【二分】LOJ 1048 Conquering Keokradong

KIDx 的解题报告

?

题目链接：http://lightoj.com/volume_showproblem.php?problem=1048

?

题意：给n+1个数，要你通过合并使其变成k+1个数，要求令这k+1个数的最大值最小，另外输出时尽量让前面的大

#include <iostream>using namespace std;#define M 1005int n, a[M], k;bool judge (int key)//暴力检验{int i = 0, num = 0;while (i < n){int tp = a[i++];if (tp > key)//以key为最大值，因此需检验每个元素是否<=keyreturn false;for ( ; i < n; i++){if (tp + a[i] <= key){tp += a[i];num++;}else break;}}if (num >= n - k)//合并次数要符合，不可放到上面的for循环里return true; //因为还要满足每个元素都<=keyreturn false;}int main (){int t, cc = 1, l, r, mid, i, num;scanf ("%d", &t);while (t--){scanf ("%d%d", &n, &k);n++, k++;l = r = 0;for (i = 0; i < n; i++){scanf ("%d", a+i);r += a[i];}while (l < r)//二分枚举最大值{mid = (l+r) >> 1;if (judge (mid))r = mid;else l = mid + 1;}printf ("Case %d: %d\n", cc++, r);i = num = 0;/***********按题意尽量让前面的大***********/while (i < n){int tp = a[i++];if (num < n - k) for ( ; i < n; i++){if (tp + a[i] <= r){tp += a[i], num++;if (num == n - k)//合并n-k次就不能再合了！{i++; break;}}else break;}printf ("%d\n", tp);}/***********按题意尽量让前面的大***********/}return 0;}

?