贪心算法（算法竞赛、蓝桥杯）--奶牛晒衣服

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

题目链接：奶牛晒衣服 - 洛谷

#include <bits/stdc++.h> using namespace std; priority_queue<int> q;//用大根堆维护湿度的最大值 int n,a,b; int tim,maxn; int main(){ scanf("%d%d%d",&n,&a,&b); for(int i=1;i<=n;i++){ int x; scanf("%d",&x); q.push(x); } //每次找出剩余的湿度最大的衣服，使用烘干机 maxn=q.top(); q.pop(); while(maxn>tim*a){//对于最大值大于自然条件时则用烘干机 tim++; maxn-=b; q.push(maxn); maxn=q.top(); q.pop(); } //对于其他不是最大值的就能在自然条件下烘干 printf("%d",tim); return 0; } #include <bits/stdc++.h> 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<r){ mid=l+r>>1; check(mid)?r=mid:l=mid; } cout<<r; return 0; }