牛客小白月赛41 C 小红的口罩

首先很容易想到一个朴素做法，每次 $O(n)O(n)$ 寻找最小值，然后操作。

这样的复杂度是大约 $O(n^2)O(n^2)$ 的，无法通过。

然后观察该做法，发现这个 $O(n)O(n)$ 寻找最小值非常累赘。

采取小根堆每次寻找最小值、然后删除最小值、同时加入原最小值翻倍后的值，复杂度均为 $O(1)O(1)$。

大概答案最多是 $nn$ 天，于是总复杂度 $O(n)O(n)$。

代码很简短的：

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

priority_queue <ll, vector<ll>, greater<ll> > q;
//小根堆，保险地开long long

int n, k;

int main () {
    cin >> n >> k;
    
    for (int i = 1, x; i <= n; i ++) {
        cin >> x;
        
        q.push (x);
    }
    
    int sum = 0, ans = 0;
    
    while (1) {
        int t = q.top ();

        if (sum + t > k) {
            break;
        }
        
        sum += t;
        
        q.pop (), q.push (t * 2);
        
        ans ++;
    }
    
    cout << ans;
    
    return 0;
}