今天是教师节,我们做一道找到需要补充粉笔的学生编号的题目。
这道题可以使用模拟算法,但是可能时间会比较久。
所以我们可以考虑加速,将所有的同学一轮所需要的的粉笔数量计算出来,用总粉笔取余。
再进行模拟。
但我们也可以不再进行模拟,而是利用二分查找的知识来查找。
有同学可能会问,那二分查找需要建立前缀和数组并且计算,也需要花时间,并且需要空间。
这里其实我们在求和的时候就需要遍历都加一遍了,所以求前缀和和求和是可以算作同一步的,不会花更多时间。
并且我们有了前缀和数组后原数组并没有任何用处,我们可以在原数组上进行修改,不会需要新的空间。
我手写了老半天二分法,算好后上传代码想了一下还是直接利用upper_bound函数算了。
但并不是说手写二分法没有必要练习,练习可以让我们思路更清晰代码更精进。