一道简单的二分答案题……
题目描述：
把一个包含 n 个正整数的序列划分为 m 个连续的子序列(每个正整数恰好属于一个序列)。设第 i 个序列的各数之和为 S(i)，你的任务是让所有 S(i)的最大值尽量小。例如序列 1 2 3 2 5 4 划分成 3 个序列的最优方案为 1 2 3|2 5 |4，其中 S(1)、S(2)、S(3)分别为 6、7、4，最大值为 7；如果划分成 1 2|3 2|5 4，则最大值为 9，不如刚才的好。n<=10^6，所有数之和不超过 10^9。
输入格式：
第一行输入 n，m(1<=m<=n<=10^6)。
接下来一行输入 n 个正整数，每个数不超过 1000。
输出格式：
输出答案。
输入输出样例：
maxmin.in
6 3
1 2 3 2 5 4
maxmin.out
7
数据范围：
30%的数据满足：1<=m<=n<=500;
50%的数据满足：1<=m<=n<=5000;
100%的数据满足:1<=m<=n<=1000000。
我的解析：
很多人会想到动态规划，用数组dp[i][j]表示前i个数字分成k份什么的。但是这个10^6的数据肯定会超时。
那么怎么办呢？贪心肯定解不了，搜索也会炸，那就得找一个速度快的方法，那就是二分答案。
这道题二分答案的主要思想是：从一个大区间内取中点mid当做这组数据的解，然后枚举序列里的数字，每当连续数字的和接近于且小于等于mid，那就把他们分成一组。如果总共分成的组数k大于要求的组数n，那就说明mid取小了，在l~mid里重新找；如果总共分成的组数k小于要求的组数n，那说明mid的取小了，在mid+1~r里重新找；如果k已经等于n，那么就把[l,r]区间一直往左缩（像[l,r] => [l,mid] mid=(l+r)/2 这个样子）直到l==r 输出答案。
我的代码：
#include<cstdio> #include<algorithm> using namespace std; long long num[1000005]; long long sum[1000005]; int ans = 0; int n,k; int kato(int l,int r) { if(l == r) return l; int cnt = 1; int p = 0; int mid = (r + l) / 2; for(int i=1;i<=n;i++) { if(sum[i] - sum[p] > mid) { p = i - 1; cnt++; } } if(cnt <= k) r = mid; else l = mid + 1; return kato(l,r); } void redo() { scanf("%d%d",&n,&k); for(int i=1;i<=n;i++) { scanf("%lld",&num[i]); sum[i] = num[i] + sum[i-1]; } } void dokumento() { // freopen("maxmin.in","r",stdin); // freopen("maxmin.out","w",stdout); } void porito() { printf("%d",kato(0,2e6 + 5)); } void solve() { dokumento(); redo(); porito(); } int main() { solve(); return 0; }