【题解】Luogu P1843 奶牛晒衣服

基本算法1-1/2-3

堆贪心

贪心每次取湿度最大的，堆维护

code

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 namespace gengyf{
 4 const int maxn=5e5+10;
 5 inline int read(){
 6     int f=1,x=0;char s=getchar();
 7     while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
 8     while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
 9     return f*x;
10 }
11 int n,a,b,wet[maxn],t;
12 priority_queue<int>q;
13 int main(){
14     n=read();a=read();b=read();
15     for(int i=1;i<=n;i++){
16         wet[i]=read();
17         q.push(wet[i]);
18     }
19     while(q.top()-a*t>0){
20         t++;int x=q.top();
21         x-=b;q.pop();q.push(x);
22     }
23     printf("%d",t);
24     return 0;
25 }
26 }
27 signed main(){
28   gengyf::main();
29   return 0;
30 }

贪心

二分

二分天数，判断用mid天能否把衣服都弄干

code

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int n,a,b,t[500010];
 4 long long l,r;
 5 int main(){
 6     scanf("%d%d%d",&n,&a,&b);
 7     for(register int i=0;i<n;i++){
 8         scanf("%d",&t[i]);
 9         r+=t[i];
10     }
11     long long mid;
12     while(l<=r){
13         int h=0;
14         mid=(l+r)/2;
15         for(int i=0; i<n; i++)
16             if(t[i]-a*mid>0)
17                 h+=(t[i]-a*mid)%b==0?(t[i]-a*mid)/b:(t[i]-a*mid)/b+1;
18         if(h<=mid)r=mid-1;
19         else l=mid+1;
20     }
21     printf("%lld",l);
22     return 0;
23 }

怕不是开始刷水题了