Monthly Expense(最大值最小化问题)

POJ-3273

Monthly Expense

Time Limit: 2000MS		Memory Limit: 65536K
Total Submissions: 10557		Accepted: 4311

Description

Farmer John is an astounding accounting wizard and has realized he might run out of money to run the farm. He has already calculated and recorded the exact amount of money (1 ≤ money_i ≤ 10,000) that he will need to spend each day over the next N (1 ≤ N ≤ 100,000) days.

FJ wants to create a budget for a sequential set of exactly M (1 ≤ M ≤ N) fiscal periods called "fajomonths". Each of these fajomonths contains a set of 1 or more consecutive days. Every day is contained in exactly one fajomonth.

FJ's goal is to arrange the fajomonths so as to minimize the expenses of the fajomonth with the highest spending and thus determine his monthly spending limit.

Input

Line 1: Two space-separated integers: N and M
Lines 2..N+1: Line i+1 contains the number of dollars Farmer John spends on the ith day

Output

Line 1: The smallest possible monthly limit Farmer John can afford to live with.

Sample Input

Sample Output

Hint

If Farmer John schedules the months so that the first two days are a month, the third and fourth are a month, and the last three are their own months, he spends at most $500 in any month. Any other method of scheduling gives a larger minimum monthly limit.

Source

USACO 2007 March Silver

还是显神的指点，今天告诉我有最大值最小化这么个东西

总结一下最大值最小化的思路

其实觉得这种算法蛮有现实意义的，给一堆乱七八糟的东西分堆，分出来的每堆都不超过一个固定的数值，这是要有技术含量的。

用到二分我也觉得一开始没想到，现在觉得确实用二分挺合理的

1.即首先求出二分的上下限，这个是每次二分必做的准备工作，上限即为这一堆东西的总量，下限即单个最大的物品的值。

2.有上下限之后即开始二分，最难写的部分就出来了，即判断当前分堆是否合理，在判断分堆是否合理中，主要的限制因素为两个，一个是单堆的量肯定不能超过当前的Mid值，另一个是分出的堆数一定不能超过题目要求的M值

3.由判断条件即可将二分范围进行缩小，即，一旦当前Mid值满足分堆要求，意味着我还可以把Mid值缩小，即把二分的right=mid，如果当前Mid值触犯了判断条件，即说明当前值还太小，即把left=mid。

4.由以上二分return出来的结果即为所求值

#include <iostream>
#include <cstdio>
#define maxn 100005
using namespace std;
int cost[maxn];
int n,m;
bool judge(int x)//用来判断按当前二分值作为题目要求的最大值，所分出的堆是否合理。
{
    int s=0,t=0;
    for (int i=0;i<n;i++)
    {
        if (cost[i]>x) return false;
        if (s+cost[i]>x)
        {
            if (t>=m-1) return false;
            t++;
            s=cost[i];
        }
        else
        s+=cost[i];
    }
    return true;
}
int binary(int max,int sum)  //二分部分
{
    int mid,left=max,right=sum;
    while (left<right)
    {
        mid=left+(right-left)/2;
        if (!judge(mid)) left=mid+1;
        else
        right=mid;
    }
    return left;
}
int main()
{
    int max=0;//二分的下界
    int sum=0;//二分的上界
    scanf("%d%d",&n,&m);
    for (int i=0;i<n;i++)
    {
        scanf("%d",&cost[i]);
        max=max>cost[i]?max:cost[i];
        sum+=cost[i];
    }
    printf("%d
",binary(max,sum));
    return 0;
}

　　此外，提醒一下，POJ上的这道题目如果用cin cout会TLE，估计是数据量的问题，建议用C的输入输出