http://poj.org/problem?id=3104

題目大意：

有n件衣服，每件有ai的水，自然風(fēng)干每分鐘少1，而烘干每分鐘少k。求全部弄干的最短時(shí)間。

思路：

注意烘干時(shí)候沒有自然風(fēng)干。

可以理解為烘干時(shí)每分鐘掉(k-1)的水。

這樣每件衣服每分鐘就都掉1水了。

二分枚舉最小值即可。

#include<cstdio> #include<algorithm> 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<n;i++) scanf("%d",&a[i]);scanf("%d",&k);sort(a,a+n);if(k==1){printf("%d\n",a[n-1]);continue;}int ans;int L=1,R=a[n-1];while( L <=R ){int mid=L+(R-L)/2;if(ok(mid)) {R=mid-1;ans=mid;}elseL=mid+1;}printf("%d\n",ans);}return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/murmured/p/5004035.html

總結(jié)

以上是生活随笔為你收集整理的POJ 3104 Drying 二分的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。