P1843 奶牛晒衣服

Hypnotize · 2021-06-05 16:06:24 · 个人记录

二分答案练手题。

代码里有非常详尽的注释。

代码：

#include<bits/stdc++.h>
using namespace std;
int l=0,r=500010;
int n,a,b;
int c[500005];
int zxc,xjy;
int i;
int mid;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}//非正经快读 
bool check(int x){//x为烘干机可使用时间 
    xjy=x;//为了不影响x的值...其实没用 
    for(i=1;i<=n;i++){
        zxc=c[i]-a*x;//这件衣服剩余的湿度 
        if(zxc<=0) continue;//如果干了就不考虑了 
        int lsy=zxc/b;//lsy为烘干这件衣服所需的烘干机使用时间 
        if(zxc%b>0) lsy++;//超出则加一 
        xjy=xjy-lsy;//烘干机总使用时间减少 
        if(xjy<0) return false;//烘干机总使用时间减到负数说明就算用了烘干机也烘不干 
    }
    if(xjy>=0) return true;
               else return false;//这句也没什么用 
}
int main(){
    n=read();
    a=read();
    b=read(); 
    for(i=1;i<=n;i++){
        c[i]=read();
    }
    while(l<r){
        mid=(l+r)>>1;
        if(check(mid)) r=mid;else l=mid+1;
    }//二分答案标程，缩小答案区间直到求出答案 
    printf("%d",l);
    return 0;
}