解题思路:一开始想的是用贪心去解,做完发现只得了36分,动态规划想不来,做完某个二分答案得题目后发现能用二分答案去解这道题
用二分法去枚举要烘干衣服最少用多少时间.
注意事项:
参考代码:
#include<bits/stdc++.h> using namespace std; int n,a,b; int y[500005]; int check(int t) { int x[500005]; for(int i=0;i<n;i++) { x[i]=y[i]; } for(int i=n-1;i>=0;i--)//自然风干的量 { x[i]-=t*a; if(x[i]<0) { x[i]=0; } } for(int i=n-1;i>=0;i--)//最好得肯定每一个单位时间都要用上烘干机 { t-=x[i]/b; if((x[i]/b)*b!=x[i]) { t--; } } if(t>=0)//烘干机没有用完,说明时间或许可以再减少 { return 1; } else { return 0; } } int main() { scanf("%d%d%d",&n,&a,&b); for(int i=0;i<n;i++) { scanf("%d",&y[i]); } sort(y,y+n); int l=1,r=y[n-1]; int ans; while(l<=r) { int mid=(l+r)>>1; //printf("%d",mid); if(check(mid)==1) { ans=mid; r=mid-1; } else if(check(mid)==0) { l=mid+1; } } printf("%d",ans); return 0; }
0.0分
1 人评分