POJ3273--Monthly Expense

1144 ワード

Farmer Johnは毎日支出する勘定書があって、彼は今これらの日をいくつかの部分に分けたいと思って、各部分は1つのFJ月と呼ばれて、どのように分解して、FJ月の最大値を最小にします
 
解析:最大値を最小化します.ちょくせつにぶん
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; }