給你n個數表示含水量,給你一個k表示每分鐘洗衣機能脫水k滴 每分鐘沒有在洗衣機的衣服自動脫水一滴,求把全部水托干最小時間,怎麼都沒想到居然是二分;==!!
好吧,二分枚舉最小時間mid,然後求實際所需時間再 經行判斷, 如果枚舉時間為mid,對每件衣服num【i】 如果num【i】小於mid 很顯然直接自然干最好 而對於num【i】大於mid所用時間為t,設自然干時間為x1 用洗衣機的時間為x2, 很顯然 x1+x2小於等於mid x2*k+x1小於等於num【i】 可以求出t小於等於(num【i】-mid)/(k-1) 這裡要注意應為衣服一定要全干 **所以存在一個取整的操作** 把所有t加起來與mid判斷就ok了
#include#include #include #include using namespace std; __int64 num[100010]; int max(int a,int b) { return a>b?a:b; } int main() { int n,i,j,k; while(~scanf("%d",&n)) { __int64 left=1,right=0,mid; for(i=1;i<=n;i++) { scanf("%I64d",&num[i]); right=max(right,num[i]); } scanf("%d",&k); if(k==1) printf("%I64d\n",right); else { __int64 ans; while(left<=right) { mid=(left+right)/2; __int64 sum=0; for(i=1;i<=n;i++) if(num[i]>mid) { sum+=ceil((double)(num[i]-mid)/(double)(k-1)); } if(sum<=mid) { ans=mid; right=mid-1; } else left=mid+1; } printf("%I64d\n",ans); } } return 0; }