题目来源：https://ac.nowcoder.com/acm/problem/229953
这算是期末周结束回归的第一篇文章，补一下19号的档。我们拿到题目首先开始思考，对于一个口罩，我们自然希望在不舒服度不超过 k 的前提下尽可能多撑几天。想要“多撑几天”，就是每天都要尽可能减少口罩对不舒服度的累加，所以对每一天的所有口罩，我们都选取不舒服度最小的进行佩戴，然后当天戴完我们先将口罩都回收，回收操作意味着当天用过的口罩不舒服度会翻倍。
由于数据量上只有1e5的大小，首先肯定希望能通过模拟法解决问题。针对上面的分析，我们最会需要用到的操作就是对口罩们进行不舒服度排序。有没有什么数据结构能实现自动排序，并且复杂度很小的呢？有的兄弟有的，我们的 Priority_queue 优先队列就是这种可以自动对数据进行排序的结构。
具体实现上，我们开一个优先队列（小顶堆，记得在定义的时候用 greater 方法），然后正常读入所有初始值。由于优先队列本质是一个堆，所以每次操作进来的时候会自动排序而且复杂度非常可观。接下来，在累计不舒服度不超过 k 的前提下每天都取出不舒服度最小的口罩使用（元素出队），累计天数增加一天，然后将出队元素翻倍后重新入队。如此直到不舒服度大于 k ，就可以得到我们的答案。
额外拓展一下，有一个性能比较的问题。如果是 vector 加 sort 函数性能会好吗？如果是优先队列方案，假设有 n 个元素进行 m 次操作，将会有下面的情况：
priority_queue<int> pq;
//初始化用O(n)
//每一次操作
pq.pop();//O(log n)
pq.push(x);//O(log n)
//一共消耗时间 O(mlog n)但是 vector 配合 sort 方案效果就是灾难级的：
vector<int> vec;
sort(vec.begin(),vec.end()); //每次排序都是O(nlog n)
vec.erase(find_min());//查找和移动各需要O(n)的时间
vec.push_back(new_val);//入队 我们甚至都不考虑他了
sort//略写了，总之又是O(nlog n)
//上述情况下 一共消耗时间 O(m*nlog n)因此，在考虑数据结构的时候，我们尽可能从性能方面也照顾到数据规模和耗时，避免由于优化考虑不足多wa一发提交。
Comments NOTHING