POJ 3273 Monthly Expense

Description

n天预算花费分为m组（可少于m），所有组中最大值最小是多少？

题目链接

思路

二分查找，最小化最大值

二分三要素：

1. 下界：(n天预算分为n组)，此时答案为n天预算中的最大值

2. 上界：(n天预算分为1组)，此时答案为n天预算之和

3. bool judge(int mid)函数：

   “连续”是前提，贪心性分组

   分完之后，

   if 组数 <= m return 1 可再优化（最小化最大值）：上界更新为mid

   else return 0 下界更新为 mid + 1

Code

#include <cstdio>
#include <iostream>
using namespace std;
const int INF = 0x3f3f3f3f;

int n, m, b[100005];

bool judge(int ans)
{
    int sum = 0, num = 1;///每组的和与组数
    for(int i = 0; i < n; ++i)
    {
        if(sum + b[i] <= ans)
            sum += b[i];
        else
        {
            sum = b[i];
            num++;
        }
    }
    if(num <= m)
        return 1;
    else
        return 0;
}

int main()
{
    while(~scanf("%d%d", &n, &m))
    {
        int l = 0, r = 0;
        for(int i = 0; i < n; ++i)
        {
            scanf("%d", &b[i]);
            r += b[i];
            if(l < b[i])///所有值里最大的
                l = b[i];
        }
        int mid;
        ///最小化最大值
        while(l < r)
        {
            mid = (l + r) >> 1;
            if(judge(mid))///中值可以，上界降低
                r = mid;
            else
                l = mid + 1;
        }
        cout << l << '\n';
    }
    return 0;
}