POJ3273 Monthly Expense

时间:2021-07-07 16:55:55

  查看原题

  边界,就是边界和思维,怎么有效的判断中间值是大了还是小了,以及准确的找到边界!一个<写成<=就前功尽弃,还特别难找到错误!

 #include <cstdio>
#include <algorithm>
const int maxN = ;
int N, M;
int A[maxN];
using namespace std;
int main(void) {
while ( == scanf("%d%d", &N, &M)) {
int u = , l = , m, sum, cnt, i;
for (int i = ; i < N; i++) {
scanf("%d", &A[i]);
u += A[i];
l = max(l, A[i]);
}
while (u > l) {
m = (l+u)>>;
sum = cnt = ;
for (i = ; i < N; i++) {
sum += A[i];
if (sum > m) {
cnt++;
sum = A[i];
}
}
if (cnt < M) u = m;
else l = m+;
}
printf("%d\n", l);
}
}