题目背景
熊大妈决定给每个牛宝宝都穿上可爱的婴儿装 。 于是 , 为牛宝宝洗晒衣服就成了很不爽的事情。
题目描述
熊大妈请你帮助完成这个重任 。 洗完衣服后 , 你就要弄干衣服 。 衣服在自然条件下用 1 的时间可以晒干 A 点湿度 。 抠门的熊大妈买了 1 台烘衣机 。使用烘衣机可以让你用 1 的时间使 1 件衣服除了自然晒干 A 点湿度外,还可以烘干 B 点湿度,但在 1 的时间内只能对 1 件衣服使用。N 件衣服因为种种原因而不一样湿 , 现在告诉你每件衣服的湿度 , 要你求出弄干所有衣服的最少时间(湿度为 0 为干) 。
输入输出格式
输入格式:
第一行 N , A , B ;接下来 N 行,每行一个数,表示衣服的湿度( 1 ≤ 湿度, A , B ≤ 500000 , 1 ≤ N ≤ 500000 ) 。
输出格式:
一行,弄干所有衣服的最少时间。
输入输出样例
说明
第 1 个时间内,用机器处理第 3 件衣服,此外,所有衣服自然晒干 。 花费 1 时间全部弄干。
分析:
本题同样不难想到是二分答案。而至于判断函数(即OK函数)则可以用贪心来求解,即对于每一件衣服,只有无法完成时再用烘干机,负责不用。
CODE:
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cstring> 5 using namespace std; 6 int n,a,b; 7 int wet[500005]; 8 bool ok(int k){ 9 int time=0; 10 for (int i=1;i<=n;i++){ 11 if (wet[i]>a*k){ 12 time+=(wet[i]-a*k)/b; 13 if ((wet[i]-a*k)%b!=0) time++; 14 } 15 if (time>k) return false; 16 } 17 if (time>k) return false; 18 return true; 19 } 20 int main(){ 21 cin>>n>>a>>b; 22 int r=0; 23 for (int i=1;i<=n;i++) 24 cin>>wet[i],r=max(r,wet[i]); 25 int l=1; 26 while (l<=r){ 27 int mid=(l+r)/2; 28 if (ok(mid)) r=mid-1; 29 else l=mid+1; 30 } 31 cout<<l<<endl; 32 //system("pause"); 33 return 0; 34 }