题目大意
将 个数分成 段，使每段总和的最大值最小。
分析
设 个数分别为 ， ，， 。
若我们可以假设这个最大值最小为 ，则 最小为数列中的最小值 ，也不可能超过 个数的总和 ，所以 ，由于 与 足够小，所以我们可以在 到 暴力枚举 。
有了 ，接下来就要验证 是否合理或者达到最小。我们定义 函数。开辟一个数组 用于记录每段的开头与结尾。定义 用于记录当前的子段的值， 用于记录目前已分的段数。
考虑到在最大值相同时，前面的子段的和达到最小，所以循环要从 到 。假如 ，说明 已达上限，那么记录右端点 ，同时新开一段，即 ，再记录新子段的左端点 记得把 变为 。否则 。
具体 函数代码如下：
bool check(int x){
int t[501][3];
memset(t, 0, sizeof(t));
t[1][2] = m; //最后一个子段的右端点是m
int n = 1, total = a[m]; //最初有1个子段，且已经选取了一个数，所以total=a[m]
for(int i = m - 1;i >= 1;--i){
if(total + a[i] > x){ //达到上限x
t[n][1] = i + 1; //记录右端点
n++;
t[n][2] = i; //记录左端点
total = a[i]; //初始值即目前选取的这个数
}
else{
total += a[i]; //未达上限，继续挑数
}
}
t[n][1] = 1; //最前一个的子段的左端点端点为1
if(n > k){
return 0; //选取的子段个数不可能比k大
}
for(int i = 1;i <= n;i++){
ans[n + 1 - i][1] = t[i][1];
ans[n + 1 - i][2] = t[i][2];
} //用ans数组记录左右端点
return 1;
}
其实最大值 也可不枚举，用二分答案会更快。如下：
while(s <= e){
int mid = (s + e) / 2;
if(check(mid)){
e = mid - 1;
}
else{
s = mid + 1;
}
}
其中最初 为 ， 为 。
AC代码
#include <bits/stdc++.h>
using namespace std;
int m, k, a[501];
int ans[501][3];
bool check(int x){
int t[501][3];
memset(t, 0, sizeof(t));
t[1][2] = m;
int n = 1, total = a[m];
for(int i = m - 1;i >= 1;--i){
if(total + a[i] > x){
t[n][1] = i + 1;
n++;
t[n][2] = i;
total = a[i];
}
else{
total += a[i];
}
}
t[n][1] = 1;
if(n > k){
return 0;
}
for(int i = 1;i <= n;i++){
ans[n + 1 - i][1] = t[i][1];
ans[n + 1 - i][2] = t[i][2];
}
return 1;
}
int main() {
scanf("%d%d", &m, &k);
int s = INT_MAX, e = 0;
for (int i = 1; i <= m; ++i) {
scanf("%d", &a[i]);
s = min(s, a[i]); //选取最小值，子段和最小值必定大于等于数组中最小值
e += a[i]; //求和，子段和最大值必定小于等于所有数总和
}
while (s <= e) {
int mid = (s + e) / 2;
if (check(mid)) {
e = mid - 1;
} else {
s = mid + 1;
}
}
for (int i = 1; i <= k; ++i) {
printf("%d %d\n", ans[i][1], ans[i][2]);
}
return 0;
}
暴力枚举只用把
while (s <= e) {
int mid = (s + e) / 2;
if (check(mid)) {
e = mid - 1;
} else {
s = mid + 1;
}
}
改为
for(int i = s;i <= e;i++){
if(check(i)){
break;
}
}
也可 。