概述
题目描述：晾衣服，洗衣机一分钟可以晾K水，自然风干一分钟可以减少1水。求晾干所有衣服所需要的最小时间。
解题思路：二分时间，那怎么计算满足的时间呢。转换一下思路，总时间就是洗衣机工作的时间，因为如果只有自然风干的话，时间是<=洗衣机总是工作的，什么时候=呢，是k=1的时候。那么下面计算洗衣机工作的时间，列一个方程组，求每件衣服需要洗衣机洗的时间t2。t1*1+t2*k>=w[i],t1+t2=mid（每次二分的总时间），t1是自然风干的时间。得出t2>=(w[i]-mid)/(k-1),如果(w[i]-mid)%(k-1)！=0，那么t2就得+1.另外还需要注意的地方时分母k-1不能等于0，所以需要特殊处理。
代码如下：
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=100000+10;
int w[maxn],n,k;
bool judge(int mid)
{
int tol=0;
for(int i=0;i<n;i++)
{
if(w[i]-mid>0)
{
if(k==1) tol+=(w[i]-tol);
else
{
if((w[i]-mid)%(k-1)) tol+=(w[i]-mid)/(k-1)+1;
else tol+=(w[i]-mid)/(k-1);
}
}
if(tol>mid) return false;
}
return true;
}
int main()
{
scanf("%d",&n);
int mmax=-1;
for(int i=0;i<n;i++)
{
scanf("%d",w+i);
mmax=max(mmax,w[i]);
}
scanf("%d",&k);
sort(w,w+n,greater<int>());
int l=0,r=mmax*2,ans=l+(r-l)/2;
while(r-l>1)
{
int mid=l+(r-l)/2;
if(judge(mid))
{
ans=mid;
r=mid;
}
else l=mid;
}
cout << ans << endl;
return 0;
}
另外二分的时候控制条件和边界处理，还有输出哪一个变量都是些小细节，需要考虑。比如控制条件是r-l>1,那么只需要如上代码那样就行，输出可以是最后的mid或r。如果控制条件是r>=l,则需要写成r=mid-1,l=mid+1,这样才能保证跳出循环，最后可以输出最后的mid或者l。如果控制条件是r>l，则得写成l=mid+1,r=mid，这样才能保证跳出循环，最后可以输出最后的mid或l。最后总结r和l为什么要这样写的，因为要保证能跳出循环，使得l可以大于r,如果只是让r=mid,l=mid，则二分到最后，r-l=1,永远跳不出循环,所以循环控制条件写成r-l>1也是可行的。
之前做浮点数的二分题，二分到最后，l,r,mid相差极其微小，所以是在误差范围之内的，最后输出lr,mid都行，但做整型数的时候，二分到最后l,r相差1,具体输出哪一个就不一样了，但是无论是浮点数还是整型数，最后输出mid应该不会错。
最后
以上就是粗心小蘑菇为你收集整理的Drying POJ - 3104的全部内容，希望文章能够帮你解决Drying POJ - 3104所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复