【题目来源】
洛谷：P1843 奶牛晒衣服 - 洛谷
【题目描述】
熊大妈决定给每个牛宝宝都穿上可爱的婴儿装 。但是由于衣服很湿，为牛宝宝晒衣服就成了很不爽的事情。于是，熊大妈请你（奶牛）帮助她完成这个重任。
一件衣服在自然条件下用一秒的时间可以晒干 \(a\) 点湿度。抠门的熊大妈只买了一台烘衣机 。使用用一秒烘衣机可以让一件衣服额外烘干 \(b\) 点湿度（一秒晒干 \(a+b\) 湿度），但在同一时间内只能烘一件衣服。现在有 \(n\) 件衣服，第 \(i\) 衣服的湿度为 \(w_i\)（保证互不相同），要你求出弄干所有衣服的最少时间（湿度为 \(0\) 为干 ）。
【输入】
第一行三个整数，分别为 \(n,a,b\)。
接下来 \(2\) 到 \(n+1\) 行，第 \(i\) 行输入 \(w_i\)。
【输出】
一行，弄干所有衣服的最少时间。
【输入样例】
3 2 1
1
2
3
【输出样例】
1
【算法标签】
《洛谷 P1843 奶牛晒衣服》 #模拟# #贪心# #二分#
【代码详解】
#include <bits/stdc++.h>
using namespace std;int n; // 衣服数量
int a; // 自然晾干速度
int b; // 烘干机烘干速度
priority_queue<int> q; // 大根堆，存储衣服湿度
int tim = 0; // 总时间
int mx; // 当前最大湿度int main()
{// 输入衣服数量、自然晾干速度和烘干机烘干速度cin >> n >> a >> b;// 输入每件衣服的初始湿度for (int i = 1; i <= n; i++){int x;cin >> x;q.push(x); // 将湿度加入优先队列}// 初始化当前最大湿度mx = q.top();q.pop();// 循环处理直到最大湿度满足条件while (mx > tim * a){tim++; // 时间增加1单位mx -= b; // 使用烘干机烘干q.push(mx); // 将处理后的湿度重新放入队列mx = q.top(); // 获取新的最大湿度q.pop();}// 输出总时间cout << tim;return 0;
}
【运行结果】
3 2 1
1
2
3
1