题解 | #向上取整#
向上取整
https://ac.nowcoder.com/acm/contest/21041/F
本题是一道构造题,考察思维。构造方案不唯一,我来讲讲我的思路。
- 对于任意两个相邻的数i,i+1来说,如果让左边的数成为被除数,右边的数成为除数,那么一定可以让左边的数变成1
- 如果这样一直推下去,可以让除了最后一个数以外的其他所有数都变成1,但这样最后一个数n就动不了了
- 考虑留一个数出来和n辗转相除,这里你可以有很多选择,我选择了8,8可以覆盖题目数据范围,最后再将8变成1即可。
代码: https://ac.nowcoder.com/acm/contest/view-submission?submissionId=48975720
算法竞赛之路 文章被收录于专栏
整理、记录算法竞赛的好题