题解 P1182 【数列分段 Section II】
本题数据范围有误
这题非常水，注意查找区间的控制。我这个题解重点不讲思路，而是
指出本题的一个漏洞：数据范围有误。
思路大佬们都说过了，每次猜测一个答案，即可行区间的最中间，当合法（也就是分的段数小于等于规定段数）时，可以继续减小；否则应当增大。不过，这个和二分查找不完全相同。
区间之和可以用前缀和来描述。sum[i] += sum[i - 1];
这样，由于每一项都是非负，sum数组是单调递增（严格说是非单调递减）的。因此，我们在找不大于某个和的某一段时，可以使用upper_bound。
开始是这样写的：
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
int sum[100001];
int main()
{
int k, l, r, mid, n, i, cnt, tmp = 0;
scanf("%d %d", &n, &k);
for (i = 1; i <= n; i++)
{
scanf("%d", &sum[i]);
if (sum[i] > tmp) tmp = sum[i];
sum[i] += sum[i - 1];
}
l = tmp, r = sum[n];
while (l < r)
{
mid = l + ((r - l) >> 1);
tmp = cnt = 0;
i = 1;
while (cnt <= k && i <= n)
{
i = upper_bound(sum + i, sum + n + 1, tmp + mid) - sum;
tmp = sum[i - 1];
cnt++;
}
if (cnt > k) l = mid + 1;
else r = mid;
}
printf("%d", r);
return 0;
}但是，很奇怪的，WA第五个点。下载了一下，这个点真有100000个整数。
借助Clion（不是打广告，但jetbrains的IDE真的做得很好）强大的调试功能，我尝试观察sum的元素，发现竟然出现了负值！很明显，int溢出了。因此，在查找的过程中，upper_bound出现了问题。
全部改成long long就过了：
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
long long sum[100001];
int main()
{
int k, n, i, cnt;
long long tmp = 0, l, r, mid;
scanf("%d %d", &n, &k);
for (i = 1; i <= n; i++)
{
scanf("%lld", &sum[i]);
if (sum[i] > tmp) tmp = sum[i];
sum[i] += sum[i - 1];
}
l = tmp, r = sum[n];
while (l < r)
{
mid = l + ((r - l) >> 1);
tmp = cnt = 0;
i = 1;
while (cnt <= k && i <= n)
{
i = upper_bound(sum + i, sum + n + 1, tmp + mid) - sum;
tmp = sum[i - 1];
cnt++;
}
if (cnt > k) l = mid + 1;
else r = mid;
}
printf("%lld", r);
return 0;
}而调试器告诉我，这组数据所有整数之和大约是
另外，我还尝试了不用upper_bound的做法：
tmp = cnt = 0;
i = 1;
while (cnt <= k && i <= n)
{
while (i <= n && sum[i] - tmp <= mid) i++;
tmp = sum[i - 1];
cnt++;
}发现这样也能AC！这是因为，二进制减法的基本性质！即使被减数和减数超int，只要差不超int，则结果依然正确。了解一下就好了，要是仔细解释，可以写三大张纸了(*╹▽╹*)。
原来，数据范围限制