题目大意:
有n件衣服,每件有ai的水,自然风干每分钟少1,而烘干每分钟少k。求所有弄干的最短时间。
思路:
注意烘干时候没有自然风干。
能够理解为烘干时每分钟掉(k-1)的水。
这样每件衣服每分钟就都掉1水了。
二分枚举最小值就可以。
#include#include using namespace std;const int MAXN=100000+10;int a[MAXN];int n,k;bool ok(int x){ int t=0; for(int i=n-1;i>=0;i--) { if(a[i]<=x) break; else t=t+(a[i]+k-2-x)/(k-1); if(t>x) return false; } return true;}int main(){ while(~scanf("%d",&n)) { for(int i=0;i