题目链接:
http://http://poj.org/problem?id=3104
题意:你有n件湿度为a[i]的衣服需要晾干,每件衣服每分钟可以蒸干1个湿度,烘干机每分钟可以烘干k个湿度,烘干时不计蒸干,烘干机每次只能烘干一件衣服,问把这n件衣服晾干所需的最少时间。
思路:二分结果。
1.当k==1时,所需时间为n件衣服中湿度最大的值。
2.当k>1时,二分所需时间,求出结果。
参考代码:
#include <iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
#include<stack>
#include<cstring>
#define max(a,b) a>b?a:b
#define ll long long
#define inf 0x3f3f3f3f
using namespace std;
ll a[100010];
ll k,maxx;
int n;
bool check(ll x)
{
ll ans=0;
for(int i=0;i<n;i++)
{
if(a[i]>x)//湿度>所需时间,用烘干机烘干
{
ll t=ceil((a[i]-x)*1.0/(k-1));//ceil()函数是求不小于给定实数的最小整数,如:ceil(2.3)=3
ans+=t;
}
}
if(ans<=x)
return true;
return false;
}
int main()
{
while(~scanf("%d",&n))
{
maxx=0;
for(int i=0;i<n;i++)
{
scanf("%lld",&a[i]);
maxx=max(maxx,a[i]);
}
scanf("%lld",&k);
if(k==1)
{
printf("%lldn",maxx);
continue;
}
ll L=1,R=maxx,mid=(L+R)/2;
while(L<R)
{
if(check(mid))
R=mid;
else
L=mid+1;
mid=(L+R)/2;
}
printf("%lldn",mid);
}
return 0;
}
最后
以上就是平常香菇最近收集整理的关于POJ-3104 Drying的全部内容,更多相关POJ-3104内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
发表评论 取消回复