POJ3273--Monthly Expense
1144 ワード
Farmer Johnは毎日支出する勘定書があって、彼は今これらの日をいくつかの部分に分けたいと思って、各部分は1つのFJ月と呼ばれて、どのように分解して、FJ月の最大値を最小にします
解析:最大値を最小化します.ちょくせつにぶん
C(tot)関数は、FJ月ごとの総支出がtotを超えないかどうかを判断するために使用される.
解析:最大値を最小化します.ちょくせつにぶん
C(tot)関数は、FJ月ごとの総支出がtotを超えないかどうかを判断するために使用される.
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 111111;
int n, m;
int x[maxn];
bool C(int tot) {
int last = 0; //last
for(int i = 1; i <= m; i++) {
int cur = last;
int sum = 0; //sum FJ
while(cur < n && sum+x[cur] <= tot) {
sum += x[cur++];
}
if(cur == n) return true; // n ,
last = cur;
}
return false; // m FJ , , tot ,
}
int main() {
while(~scanf("%d%d", &n, &m)) {
for(int i = 0; i < n; i++)
scanf("%d", &x[i]);
int L = 0, R = 1 << 30;
while(R > L) {
int mid = (L+R)/2;
if(C(mid)) R = mid;
else L = mid+1;
}
printf("%d
", R);
}
return 0;
}