衡阳网站建设报价方案网站快速排名

P1843 奶牛晒衣服 【贪心】
题目背景
熊大妈决定给每个牛宝宝都穿上可爱的婴儿装 。但是由于衣服很湿，为牛宝宝晒衣服就成了很不爽的事情。于是，熊大妈请你（奶牛）帮助她完成这个重任。
题目描述
一件衣服在自然条件下用一秒的时间可以晒干 aa 点湿度。抠门的熊大妈只买了一台烘衣机 。使用用一秒烘衣机可以让一件衣服额外烘干 b 点湿度（一秒晒干 a+b 湿度），但在同一时间内只能烘一件衣服。现在有 n 件衣服，第 i 衣服的湿度为 wi （保证互不相同），要你求出弄干所有衣服的最少时间（湿度为 0 为干 ）。
输入格式
第一行三个整数，分别为 n,a,b。
接下来 2 到 n+1 行，第 i 行输入 wi 。
输出格式
一行，弄干所有衣服的最少时间。
输入输出样例
输入 #1
3 2 1
1
2
3
输出 #1
1
输入 #2
4 2 3
8 5 7 9
输出 #2
3
说明/提示
样例解释
让机器烘第三件衣服即可一秒完成。
数据范围
1≤wi ,a,b,n≤5×10^5

贪心算法操作过程：

• 最少时间取决于最后一件被弄干的衣服的时间。
• 每次找出剩余的湿度最大的衣服，使用烘干机。
• 用大根堆维护衣服的剩余湿度。
• 时间复杂度为O（nlogn）。

#include <bits/stdc++.h>
using namespace std;
int n,a,b;
int main()
{	cin>>n>>a>>b;priority_queue<int> q;for(int i=1,x;i<=n;i++){cin>>x;q.push(x);}int tpx=q.top();q.pop();int res=0;while(tpx>res*a){res++;q.push(tpx-b);tpx=q.top();q.pop();}cout<<res;return 0;
}