uva 714 Copying Books(二分法求最大值最小化)

题目连接:714 - Copying Books

题目大意:将一个个数为n的序列分割成m份,要求这m份中的每份中值(该份中的元素和)最大值最小, 输出切割方式,有多种情况输出使得越前面越小的情况。

解题思路:二分法求解f(x), f(x) < 0 说明不能满足, f(x) >= 0说明可以满足,f(x) 就是当前最大值为x的情况最少需要划分多少份-要求份数(如果f(x ) >= 0 说明符合要求而且还过于满足,即x还可以更小)。

注意用long long .

#include <stdio.h>
#include <string.h>
int max(const int &a, const int &b) { return a > b ? a : b;} const int N = 1005;
int n, T;
long long num[N], sum[N], rec[N]; bool judge(int Max) {
int cnt = 0, first = 0, end = 1;
while (end <= n) {
if (sum[end] - sum[first] > Max) {
cnt++;
first = end - 1;
}
end++;
}
return cnt <= T - 1;
} int main () {
long long cas, lift, right, cur;
scanf("%lld", &cas);
while (cas--) {
// Init;
memset(num, 0, sizeof(num));
memset(sum, 0, sizeof(sum));
memset(rec, 0, sizeof(rec));
lift = right = 0; // Read.
scanf("%d%d", &n, &T);
for (int i = 1; i <= n; i++) {
scanf("%lld", &num[i]);
sum[i] = sum[i - 1] + num[i];
lift = max(lift, num[i]);
}
right = sum[n]; // Count;
while (lift != right) {
cur = (right + lift) / 2;
if (judge(cur)) {
right = cur;
}
else
lift = cur + 1;
} // Draw;
long long now = 0, cnt = 0;
for (int i = n; i > 0; i--) {
if (now + num[i] > lift || i < T - cnt) {
rec[i] = 1;
cnt++;
now = num[i];
}
else
now += num[i];
} // Printf;
for (int i = 1; i < n; i++) {
printf("%lld ", num[i]);
if (rec[i]) printf("/ ");
}
printf("%lld\n", num[n]);
}
return 0;
}
上一篇:WPF中Grid的行的Height和列的Width根据内容自适应


下一篇:linux profile\bashrc\bash_profile之间的区别和联系