JDOJ 2225 工资计划

JDOJ 2225: 工资计划

https://neooj.com/oldoj/problem.php?id=2225

Description

高考结束后，同学们大都找到了一份临时工作，渴望挣得一些零用钱。从今天起，

Matrix67将连续工作N天(1<=N<=100 000)。每一天末他可以领取当天及前面若干

天里没有领取的工资，但他总共只有M(1<=M<=N)次领取工资的机会。Matrix67已

经知道了在接下来的这N天里每一天他可以赚多少钱。为了避免自己滥用零花钱，

他希望知道如何安排领取工资的时间才能使得领到工资最多的那一次工资数额最小。

注意Matrix67必须恰好领工资M次，且需要将所有的工资全部领走（即最后一天末需

要领一次工资）。

Input

第一行输入两个用空格隔开的正整数N和M
以下N行每行一个不超过10000正整数，依次表示每一天的薪水。

Output

输出领取到的工资的最大值最小是多少。

Sample Input

7 5 100 400 300 100 500 101 400

Sample Output

500

二分答案的基础题。作为本蒟蒻博客里二分答案的第一篇题解，在这里献丑讲解一下二分答案的基本实现原理及注意事项。

二分答案，就是在答案的所有可能区间里应用二分思想。

什么时候用二分答案呢？首先，要有单调性，也就是答案所在区域是单调递增或单调递减的，保证二分之后的结果仍然正确。

一般来讲，题面中出现最小值最大或者最大值最小，就可以用二分求解了。

那么我们开始二分...

二分要注意左边界和右边界，一般使用while循环实现，每次循环用mid取中间值，然后针对于中间值进行函数判断，判断此解符不符合要求，如果不符合，是大了还是小了。然后右移左端点或者左移右端点。

最后得出答案。

二分过程最重要的部分就是判断函数的书写和二分的细节。

什么是二分的细节呢？

我俗气一点说，就是+1和-1的问题，因为是整数除法，有的时候取mid的时候就会取到你不想取的地方导致答案错误，这时要仔细斟酌左移和右移到底需不需要加一或者减一。

最后，取答案的时候也要注意，你取的答案需不需要加减。

总结一下，二分思想特别容易理解，但二分细节特别容易坑爹。

那么回到本题，本题的二分很好想。

首先，答案区域的边界，以总工资为上界，以最小的单天工资为下界。

然后是判断函数，扫一遍，从第一天到第n天领工资。

如果领取的总工资tot还没有达到我们的mid，那就继续累加下一天，什么时候冒了，什么时候停止，这个时候就算是领了一次工资。

记住最后退出循环的时候也要特判，因为强制规定最后的那天也要领工资。

最后统计cnt和m的关系，合法就返回1，不合法返回0.

最后二分，结束。

代码：

#include<cstdio>
#include<algorithm>
using namespace std;
int n,m,sum,ans,maxn;
int a[100001];
bool check(int x)
{
    int tot=0,cnt=0;
    for(int i=1;i<=n;i++)
    {
        if(tot+a[i]<=x)
        {
            tot+=a[i];
            continue;
        }
        tot=a[i];
        cnt++;
    }
    if(tot>0)
        cnt++;
    if(cnt<=m)
        return 1;
    else
        return 0;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        sum+=a[i];
        maxn=max(maxn,a[i]);
    }
    int l=maxn;
    int r=sum;
    while(l<=r)
    {
        int mid=(l+r)>>1;
        if(check(mid))
            ans=mid,r=mid-1;
        else
            l=mid+1;
    }
    printf("%d",ans);
    return 0;
}

二分写法二：

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=1e5+10;
int n,m,cnt,tot;
int l,r,ll,rr;
int a[maxn];
bool check(int x)
{
    tot=0;cnt=0;
    for(int i=1;i<=n;i++)
    {
        if(tot+a[i]<=x)
        {
            tot+=a[i];
            continue;
        }
        tot=a[i];
        cnt++;
    }
    if(tot>0)
        cnt++;
    if(cnt<=m)
        return 1;
    else
        return 0;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        ll=max(ll,a[i]);
        rr+=a[i];
    }
    l=ll;r=rr;
    while(l<r)
    {
        int mid=(l+r)/2;
        if(check(mid))
            r=mid;
        else
            l=mid+1;
    }
    printf("%d",l);
    return 0;
}

JDOJ 2225 工资计划