程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> poj 3104 二分想法

poj 3104 二分想法

編輯:C++入門知識

poj 3104 二分想法


給你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;
}

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved