视频链接：A28 贪心算法 P1843 奶牛晒衣服_哔哩哔哩_bilibili

Luogu P1843 奶牛晒衣服

#include

#include

#include

#include

using namespace std;

priority_queue q; //大根堆

int n,a,b;

int tim,mx;

int main(){

scanf("%d%d%d",&n,&a,&b);

for(int i=1;i<=n;i++){

int x; scanf("%d",&x);

q.push(x);

}

//每次找出剩余的湿度最大的衣服，使用烘干机

mx=q.top(); q.pop();

while(mx>tim*a){

tim++;

mx-=b;

q.push(mx);

mx=q.top(); q.pop();

}

printf("%d",tim);

}

// 二分答案 nlogn

#include

using namespace std;

int n,a,b,w[500005];

bool check(int t){

int s=0;

for(int i=1;i<=n;i++){

if(w[i]<=t*a) continue;

s+=(w[i]-t*a+b-1)/b; //上取整

}

return s<=t;

}

int main(){

ios::sync_with_stdio(0);

cin>>n>>a>>b;

for(int i=1;i<=n;i++) cin>>w[i];

int l=0,r=1e6,mid;

while(l+1

mid=l+r>>1;

check(mid)?r=mid:l=mid;

}

cout<

}