题目描述
冬天很难洗，尤其是干衣服。但简是一个非常聪明的女孩。她不怕这个无聊的过程。 Jane 决定使用散热器来加快干燥速度。但是散热器很小，所以一次只能装一件东西。
Jane 希望在尽可能短的时间内完成干燥。她让你编写一个程序来计算给定一套衣服的最短时间。
简刚洗了n件衣服。他们每个人在洗涤过程中都服用了 ai 水。每分钟，每件物品中所含的水量减少一（当然，前提是物品尚未完全干燥）。当含水量变为零时，布变干并准备好包装。
每一分钟，Jane 都可以选择一件东西在散热器上晾干。散热器很热，所以这个东西中的水量在这一分钟内减少了 k（但不小于零——如果这个东西含有少于 k 个水，那么产生的水量将为零）。
任务是通过有效地使用散热器来最小化干燥的总时间。当所有衣服都干燥时，烘干过程结束。
输入
第一行包含一个整数 n (1 ≤ n ≤ 100 000)。第二行包含由空格分隔的 ai (1 ≤ ai ≤ 109)。第三行包含 k (1 ≤ k ≤ 109)。
输出
输出一个整数——烘干所有衣服所需的最小可能分钟数。
样本输入1
3 2 3 9 5
样本输出1
3
样本输入2
3 2 3 6 5
样本输出2
2
思路分析
使用二分枚举晒干衣服的总时间(晾干+晒干) 最长时间就是最大的采用晾干的方法.最短时间可以假定为1.然后进行枚举mid.
假设衣服a[i] > mid; 择有 a[i] = k*t + mid -t ==> t =( a[i]-mid )/(k-1); 我们处理时,只需要判断这些a[i] > mid的衣服用的烘干机时间的总和有没有超过mid,如果超过了,那肯定是不满足的.
并且当k=1时需要特殊处理, 这时候,无论使用烘干机还是晾干,最后花费时间始终等于最大湿度的衣服.
需要注意:t的结果需要向上取整,因为你的余数再用一次烘干机最多才多1个时间,但是如果选择风干,就是至少1个时间.
AC代码:
#include<iostream> #include<math.h> #include<algorithm> using namespace std; const int maxsize=100000+5; int arr[maxsize],n,k,ans; int judge(int x){ int sum1 = 0;//烘干机使用时间 for(int i = 0;i < n;i++){ if(arr[i]>x){ sum1 += ceil((arr[i]-x)*1.0 / (k-1) );// 或sum += (a[i] - x + k -2) / (k-1); } if(sum1>x){ return 0; } } return 1; } void solve(){ int l = 1,r = arr[n-1]; while(l<=r){ int mid = (l + r)/2; if(judge(mid)){ r = mid-1; // 如果是mid-1则用一个ans保存最后的值. 如果是mid则最后输出mid即可.条件也变为right-left>1 ans = mid; }else{ l = mid+1; } } } int main(){ cin>>n; for(int i = 0;i < n;i++){ cin>>arr[i]; } cin>>k; sort(arr,arr+n);//进行排序 if(k==1){//如果烘干机的速度和自动晾干速度相同,那么 需要的时间==湿度最大衣服花费的时间. cout<<arr[n-1]<<endl; return 0; } solve(); cout<<ans<<endl; return 0; }
