2 条题解
-
1
题目大意 给一个数组a,sum为a里元素的累加和,有b次将sum归零的机会,求一个最小的c,使得在合理分配b次机会的情况下sum的值无论什么时候都不超过c
思考过程 首先我们发现,如果给我们一个c,容易判断这个c能否满足条件:枚举a累加sum,当sum超过c时将sum归零,统计归零了几次即可。 所以我们就可以枚举这个c,每次判断枚举到的c是否成立,就能找到最小的c 但出题人不可能这么好心(会T) 但你都想到枚举了,还想不到二分吗?(想不到的都是自由的人)
做法 注意到,当一个c成立时,所有比它大的c都成立。 所以答案满足单调性,可以使用二分答案。 那么二分c的值,每次check一下这个c是否成立即可。 不要写死循环(@ZNB)
完结撒花!!!
信息
- ID
- 2593
- 时间
- 100ms
- 内存
- 10MiB
- 难度
- 4
- 标签
- 递交数
- 25
- 已通过
- 8
- 上传者