不一样的二分;
思路:
*二分的上限下限是:MAX(最大的数字),SUM (总和);
*其中一定有一个数字满足,将N分成M份;
*求最小的;只要当它达到M份时,依然减小上届值;
算法不难,思路想到了就 水到渠成了;
/* *problem ID: POJ 3273 * Author ID: fuqiang * TIME: 2013-07-17 * Algorithm: 二分 * Status: (Accept) */ #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <string> #include <iomanip> #define maxn 100010 int a[maxn],N,M; using namespace std; inline bool check(int mid) { int num = 1, sum = 0; for(int i = 0; i <= N; i++) { if(sum + a[i] <= mid) sum += a[i]; else { sum = a[i]; num++; } } return num>M; } int main(int argc, char *argv[]) { while(scanf("%d%d",&N,&M)!=EOF) { int MAX = 0, sum = 0; for(int i = 1; i <= N; i++) { scanf("%d",&a[i]); sum += a[i]; MAX = max(MAX,a[i]); } int left = MAX, right = sum, mid; while(left < right) { mid = (left + right) / 2; if(check(mid)) left = mid + 1; else right = mid - 1; } printf("%d\n",left); } return 0; }