poj3104：Drying—贪心（二分+判定）
http://poj.org/problem?id=3104
题目
Description
It is very hard to wash and especially to dry clothes in winter. But Jane is a very smart girl. She is not afraid of this boring process. Jane has decided to use a radiator to make drying faster. But the radiator is small, so it can hold only one thing at a time.
Jane wants to perform drying in the minimal possible time. She asked you to write a program that will calculate the minimal time for a given set of clothes.
There are clothes Jane has just washed. Each of them took water during washing. Every minute the amount of water contained in each thing decreases by one (of course, only if the thing is not completely dry yet). When amount of water contained becomes zero the cloth becomes dry and is ready to be packed.
Every minute Jane can select one thing to dry on the radiator. The radiator is very hot, so the amount of water in this thing decreases by this minute (but not less than zero — if the thing contains less than water, the resulting amount of water will be zero).
The task is to minimize the total time of drying by means of using the radiator effectively. The drying process ends when all the clothes are dry.
Input
The first line contains a single integer n (1 ≤ n ≤ 100 000). The second line contains ai separated by spaces (1 ≤ ai ≤ 109). The third line contains k (1 ≤ k ≤ 109).
Output
Output a single integer — the minimal possible number of minutes required to dry all clothes.
Sample Input
sample input #1 3 2 3 9 5 sample input #2 3 2 3 6 5
Sample Output
sample output #1 3 sample output #2 2
思路
这道题可以二分总的晾干时间，注意需要理解出题目的意思，就是一件衣服可以自然烘干，也可以使用散热器烘干。所以假设一件衣服最后的烘干时间是x xx，那么我们可以假设自然烘干无时无刻不再进行，也就是说，其中有x xx的水分被自然烘干，那么对于一件包含a [ i ] a[i]a[i]水分的衣服来说：
假如a [ i ] ≤ x，那么就可以直接忽略掉，把宝贵的散热器留给其他衣服用 (continue 而不是break 在这里出过错)
假如a [ i ] > x ,那么说明这件衣服除了自然烘干外，剩下的水分必须使用散热器烘干。而需要注意的是，我们在考虑自然烘干的时候，把其设置成了每时每刻都在进行，所以，在使用散热器的对水分蒸发的贡献时，需要去掉其中预先假定包含自然烘干的时间，也就是说，原来题意中的散热器每分钟蒸发k水分，这时候单纯考虑散热器的作用时，要 k−1，即减去其中自然蒸发的贡献。
最后我们看实际需要的烘干时间和二分预期的烘干时间之间的比较进行二分决策的转移.
另外还要注意的是，这里的二分还是求的满足条件的最小下界。
【题解】
考虑将烘干机的烘干效应变为k-1，那么就是每件衣服在每秒都会自动减少一水分
如果我们知道最少需要的时间，那么每件衣服自己减少的水分数量就知道了，
在除去自然减少的水分之后，看看还需要多少k-1的水分减少才能烘干全部的衣服就可以了，
因此我们二分这个答案，验证是否可行即可。
二分+判定性（可行性）
- 选定一个时间t
- 判定是否可在t时间内完成洗衣
- 二分t选取可行的最小值
注
- 吹风机下风干速率k，是自然风干和吹风机风干的叠加，即单纯吹风机风干速率是k-1
- k==1的情况要单独考虑，因为此时k-1=0，会产生/0的异常
代码：
//2023-4-17 贪心算法中的二分策略
//最小的烘干时间 -> 采用二分策略 对时间二分 转化为判定性问题
//判定性问题 判断时间t是否可行 如果t可以烘干 ，如果t不能烘干 对t采用二分策略
//个人感觉过程中比较难的一点 当water[i]被烘干机处理时，其他的衣服也会自然晾干，会--。 如何在兼顾第i件衣服的同时，令其他的衣服也自然晾干
//烘干是一分钟减少k 自然烘干是无时无刻不再进行 也就是说 烘干机的贡献实际上是k-1 !!!!!!!!这个理解起来可能会很绕
//吹风机下风干速率k，是自然风干和吹风机风干的叠加，即单纯吹风机风干速率是k-1
//k==1的情况要单独考虑，因为此时k-1=0，会产生/0的异常
//二分+判定性（可行性）
//选定一个时间t
//判定是否可在t时间内完成洗衣
//二分t选取可行的最小值
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
const int MAXN=1e5+10;
int water[MAXN];
//判定性问题 这是贪心二分策略中最核心的部分！！！！！！！！
bool Judge(int n,int k,int time) //输入衣服的数目，烘干机的一分钟减少k，给定时间time，判定time时间内能否将衣服烘干
{
int sum=0;//所用的烘干衣服的时间 与time作比较
for(int i=0;i<n;i++)//依次对每件衣服做比较
{
// while(water[i]>time) //如果water[i]<=time 说明在给定的时间内，a[i]不用烘干机也可自然晾干
//如果water[i]>time 说明需要用烘干机
//{
// water[i]=water[i]-k;
//sum=sum+1;
// //sum=sum+ceil((water[i]-time)*1.0/(k-1));//要取上等 因为如果是water-time=4 k=6 正常的/是取下等 为了取上等 不足1的再补1 于是需要ceil
//而ceil针对浮点数，所以我们再*1.0
//老师解释的K-1 是烘干机对衣服的贡献 如果自然晾干 每分钟也是-1
// }
if(water[i]<=time)
{
// break;//出错
continue;}
else if(water[i]>time)
{
//sum=sum+ceil((water[i]-time)*1.0/(k-1));//！！！！！！！！！！！！理解困难
sum=sum+(water[i]-time)/(k-1);
if(((water[i]-time)%(k-1))!=0)
{
sum=sum+1;
}
}
if(sum>time)
return false;
}
return true;
}
int main()
{
int n,k;
scanf("%d",&n);
for(int i=0;i<n;i++)
scanf("%d",&water[i]);
scanf("%d",&k);
sort(water,water+n);//对含水量由小到大进行排序
//如果k=1，要考虑每个输入值的边界情况
if(k==1)//则自然晾干和烘干机时间一样
//不用烘干机，直接晾干取决于最大含水量的衣服
printf("%d\n",water[n-1]);
else
{
int left=1;//最小烘干时间是1
int right=water[n-1];//最长时间
while(left<=right)
{
int mid=left+(right-left)/2;
if(Judge(n,k,mid))//如果说在在时间mid中可以把衣服烘干，则试着减少mid
{
right=mid-1;
}
else{
left=mid+1;
}
}
//输出最小时间 left
printf("%d",left);
}
return 0;
}
好未来公司福利 52人发布
