题解 - 洛谷 P1843 奶牛晒衣服

题目传送门

不难看出 最易的解法就是贪心题没错！！分享一下我是怎么思考的。

贪心的思路就是执行一个死循环，每一次循环给所有衣服的湿度减去 \(A\)（自然消耗的），减过后找出里面湿度最大的给它用烘干机减去 \(B\) 点湿度。减去后再找出里面湿度最大的，如果湿度最大值小于等于 \(0\) ，说明所有衣服都干了，此时退出循环，输出循环次数。

但是这种做法存在超时的问题：

1. 每次循环里面要循环 \(n\) 次给衣服减去自然消耗的湿度
2. 每次循环里又要循环两次找两次最大值

针对这两个问题我们想出对应的优化方法：

1. 对于第 1 个问题，既然所有衣服都会减去一个相应的湿度再进行之后的比较，我们不妨不浪费时间去减，依旧不影响比较，举个例子，数列 \({5,7,3,1}\)，最大值是第二个元素 \(7\)，把所有元素都减去 2，数列变为 \({3,5,1,-1}\)，最大值依旧是第二个元素。那么针对这道题，我们干脆就不一个一个去减，依旧能找到我们要去寻找的最大值，然后给它用烘干机，给它减去 \(B\)。因为没有给每个元素减去自然湿度，我们还要考虑最后找到的最大湿度（上面的加粗部分）在减去应当减去的自然湿度之后是否小于等于 0 即可决定是否跳出循环。
2. 对于第 2 个问题，可以采用大根堆（C++ STL里内置 priority_queue），读入数据时把所有元素放进堆中，然后循环时可以直接取出最大值，取出最大值减去 \(B\)，再放回堆中，然后再检查一下 当前的最大值在减去应当减去的自然湿度之后是否小于等于 0 即可决定是否跳出循环 （见优化方法第1条）。

不理解的话可以自己带数据理解一下。

上代码：

#include <bits/stdc++.h>
using namespace std;

priority_queue<int> pq; //声明一个大根堆

//n a b见题目描述，cnt是循环变量
int n, a, b, cnt; 

int main()
{
    cin >> n >> a >> b;
    for (int i = 1; i <= n; i++) {
    	int x;		//输入这件衣服的湿度
        cin >> x;
        pq.push(x);	//把湿度值放入大根堆中
    }
    while (1) {
        cnt++;		//执行天数（循环变量）
        int x = pq.top();	//取出当前最大值（堆顶）衣服的湿度
        pq.pop();
        x -= b;		//减去b之后再放回堆中
        pq.push(x);
        if (pq.top() - cnt * a <= 0) { //判断减去应当减去的自然湿度后是否小于等于0，如果是则退出程序
            cout << cnt << endl;
            return 0;
        }
    }
}

本人蒟蒻一枚，望大佬批评指正：）