首页 > 代码库 > 【Luogu1843】奶牛晒衣服

【Luogu1843】奶牛晒衣服

点此进入原题

算法:二分答案

题解

本题算法就是二分所需的时间啦

二分答案的难点大部分都在check函数上吧

然而我居然把二分模版打错了好囧啊

总的来说这题还是不难的啊~

代码

#include<cstdio>
const int N=500005;
int n,a,b,t[N],l=0,r=N;
bool check(int x)
{
    int ret=x; //x-ret表示需要的烘干机烘干的天数。
    for(int i=1;i<=n;i++)
    {
        int tmp=t[i]-a*x; //tmp表示一件衣服x天自然烘干后的湿度
        if(tmp>0) ret-=(tmp/b+(tmp%b!=0)); //如果自然未烘干,则需要tmp/b(上取整)天来用烘干机烘干
        if(ret<0) return false; //如果烘干机烘干衣服x天不够,就return false。
    }
    return true;
}
int main()
{
    scanf("%d%d%d",&n,&a,&b);
    for(int i=1;i<=n;i++)
        scanf("%d",&t[i]);
    while(l<=r) //二分答案
    {
        int m=(l+r)/2;
        if(check(m))r=m-1; //注意:如果答案符合要求就调整右边界,使区间里的值更小
        else l=m+1;
    }
    printf("%d",r+1); //注意这里输出右边界啊(蒟蒻的我当时就这里错了QAQ)
}

 

【Luogu1843】奶牛晒衣服