本文主要是介绍POJ 3104 Drying (二分+精度),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目链接:click here~~
【题目大意】:
题意:有一些衣服,每件衣服有一定水量,有一个烘干机,每次可以烘一件衣服,每分钟可以烘掉k单位水。每件衣服没分钟可以自动蒸发掉一单位水,
用烘干机烘衣服时不蒸发。问最少需要多少时间能烘干所有的衣服。
【解题思路】:
题目数据较大,常规方法肯定会TE,首先可以想到二分枚举答案。枚举时间mid值,(一般二分的题目,题目叫你求什么,就二分什么就可以了)
那么对应两种方法
1:自然风干;2:吹风机吹干
若一件衣服的水量小于mid,则自然风干即可,否则,假设吹风机花费时间X,用于风干的时间为Y,吹风机一分钟能够吹干的水量为k,
则可得到以下两式 :
X+Y=mid;
X+Y*k>=ai ;
由以上两式可得Y>=(ai-mid)/(k -1)(关键啊!)
算出所有含水量大于mid的衣服的最小的Y(其实就是把Y相加)得到sum ,最后sum与mid比较,return y<=mid即可。
代码:
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <iostream>
#include <algorithm>
using namespace std;
const int N=1e5+10;
int a[N];
int n,m,k;
bool get(int mid)
{int y=0;for(int i=0; i<n; i++){if(a[i]<=mid) continue;else{y+=ceil((double)(a[i]-mid)/(k-1));//一定要注意精度啊,不加ceil((double))会WA啊!}if(y>mid) return false;}return y<=mid;
}
int main()
{// freopen("1.txt","r",stdin);scanf("%d",&n);int maxx=0;for(int i=0; i<n; ++i){scanf("%d",&a[i]);maxx=max(maxx,a[i]);}//cout<<"maxx=="<<maxx<<endl;scanf("%d",&k);if(k==1)printf("%d\n",maxx);else{int ll=0,rr=maxx;for(int i=1; i<=100; i++){int mid=(ll+rr)/2;if(get(mid))rr=mid;else ll=mid;}printf("%d\n",ll+1);}return 0;
}
这篇关于POJ 3104 Drying (二分+精度)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!