POJ3273 Monthly Expense（二分+贪心）

February 28, 2016

题目链接

题意：给 N 个数，划分为 M 个块（不得打乱数顺序）。找到一个最好的划分方式，使得块中的最大值最小。

二分的 l 是 N 个数的最大值，r 是 N 个数的和。

对于每个 mid 贪心遍历，看能否满足条件。

#include<iostream>
#include<cmath>
#include<queue>
#include<cstring>
#include<string>
#include<map>
#include<stack>
#include<set>
#include<cstdio>
#include<algorithm>
using namespace std;
int n, m;
int a[100005];

bool judge(int x){
    int pre = 0;
    int cnt = 0;
    for(int i = 1; i <= n; i++){
        if(a[i]-a[pre] > x){
            cnt++;
            pre = i-1;
            i--;
        }else if(i==n){
            cnt++;
        }
    }
    if(cnt <= m)
        return 1;
    else return 0;
}

int main(){
    //freopen("a.txt", "r", stdin);
    while(scanf("%d%d", &n, &m) != EOF){
        int maxx = 0, k;
        a[0] = 0;
        for(int i = 1; i <= n; i++){
            scanf("%d", &k);
            a[i] = a[i-1]+k;
            maxx = max(maxx, k);
        }
        int l = maxx, r = a[n];
        while(l <= r){
            int mid = l+(r-l)/2;
            if(judge(mid))
                r = mid-1;
            else
                l = mid+1;
        }
        cout << l << endl;
    }
    return 0;
}

Written by Armin Li , a venture capitalist. [Weibo] [Subscribe]