应该输出 l
@[残阳如血](/user/726139)
by 2011FYCCCTA @ 2023-10-28 20:11:37
@[2011FYCCCTA](/user/923403) 说得对,但是不止这一处错
by xibaohe_light @ 2023-10-28 20:38:35
@[残阳如血](/user/726139)
~~(没错我诈尸了)~~
首先二分中你的 $l$ 应当是 $a_i$ 中的最大值,因为即便是最极端情况下也会把每个数分一段。
其次就是楼上的楼上大佬说的,应当输出l而不是mid
调好的代码:
```cpp
#include <iostream>
const int MAXN = 1e5 + 10;
int N, M, l, r, mid, ans, a[MAXN];
bool check(int k) {
int cnt = 1, sum = 0;
for (int i = 1; i <= N; ++i) {
if (sum + a[i] <= k) {
sum += a[i];
continue;
}
++cnt, sum = a[i];
if (cnt > M) return false;
}
return cnt <= M && sum <= k;
}
int main() {
//freopen("P1182_4.in","r",stdin);
std::cin >> N >> M;
for (int i = 1; i <= N; ++i)
{
std::cin >> a[i];
l=std::max(l,a[i]);
r += a[i];
}
while (l <= r) {
mid = (l + r) / 2;
if (check(mid)) r = mid - 1, ans = mid;
else l = mid + 1;
}
std::cout << l;
return 0;
}
```
by xibaohe_light @ 2023-10-28 20:41:37
@[xibaohe_light](/user/601747) ~~你说得对~~。
但是最后输出 **`ans`**,$l$ 改为 $\max\{a_i\}$ 也是可以 AC 的。
并不需要输出 $l$。
[AC 记录](https://www.luogu.com.cn/record/132121604)。
突然发现 AC 后忘记删帖了,麻烦大家了,请谅解
by 残阳如血 @ 2023-10-29 18:34:33
@[残阳如血](/user/726139) 是这样的,直接输出l也可以,之所以输出mid会WA是因为有可能最后向下二分后mid并没有通过check,因此直接输出l或者在chk==true在记录答案都可以
by xibaohe_light @ 2023-10-29 19:01:17
@[残阳如血](/user/726139) 说白了,你那样也可以,但是输出l更省事
by xibaohe_light @ 2023-10-29 19:01:57
输出l可以的原因是在最后check(mid)返回false后会l=mid+1,所以这种方法和用ans记录符合条件的mid是等效的
by xibaohe_light @ 2023-10-29 19:03:29
~~再次诈尸~~
by xibaohe_light @ 2023-10-29 19:03:53