官网站站陕西省国家示范校建设专题网站

题目背景

熊大妈决定给每个牛宝宝都穿上可爱的婴儿装 。但是由于衣服很湿，为牛宝宝晒衣服就成了很不爽的事情。于是，熊大妈请你（奶牛）帮助她完成这个重任。

题目描述

一件衣服在自然条件下用一秒的时间可以晒干 a 点湿度。抠门的熊大妈只买了一台烘衣机 。使用用一秒烘衣机可以让一件衣服额外烘干 b 点湿度（一秒晒干 a+b 湿度），但在同一时间内只能烘一件衣服。现在有 n 件衣服，第 i 衣服的湿度为 wi​（保证互不相同），要你求出弄干所有衣服的最少时间（湿度为 0 为干 ）。

输入格式

第一行三个整数，分别为 n,a,b。
接下来 2 到n+1 行，第 i 行输入 wi​。

输出格式

一行，弄干所有衣服的最少时间。

输入输出样例

输入 #1复制

3 2 1
1
2
3

输出 #1复制

1

说明/提示

样例解释

让机器烘第三件衣服即可一秒完成。

解析：

我们贪心，每次烘干其时间最长的衣服。这时就需要维护大根堆，每次烘干，去最大值-b;

#include<bits/stdc++.h>
using namespace std;
struct node{int a;bool operator <(const node &b) const{return a < b.a;}
};
int main(){int n,a,b;cin >> n >> a>>b;priority_queue<node> pq;for(int i = 1;i <= n;i++){int x;cin >> x;pq.push({x});}int time = 0;int mx = pq.top().a;while(mx > time*a){//我们每次取最大的进行烘干 time++;mx -= b;pq.pop();pq.push({mx});mx = pq.top().a;} cout << time;return 0;
} 

时间复杂度为:O（logn * time）

二分法：

猜时间，对时间进行验证；

// 二分答案 nlogn
#include<iostream>
using namespace std;int n,a,b,w[500005];bool check(int t){int s=0;for(int i=1;i<=n;i++){if(w[i]<=t*a) continue;s+=(w[i]-t*a+b-1)/b; //上取整}return s<=t;
}
int main(){ios::sync_with_stdio(0);cin>>n>>a>>b;for(int i=1;i<=n;i++) cin>>w[i];int l=0,r=1e6,mid;while(l+1<r){mid=l+r>>1;check(mid)?r=mid:l=mid;}cout<<r<<endl;
}