Codeforces 1974G Money Buys Less Happiness Now

考虑到有一种贪心的思路就是能选就选。
显然这是错的，因为可能存在后面更优的情况，即当 \(c_i > c_j(i < j)\) 时，选 \(j\) 肯定比选 \(i\) 更优，因为后面剩下的更多且中间也留下了一些。

于是考虑反悔贪心。
还是一样的，如果能选就一定选上。
否则来说，考虑对于当前已经选了的中的最大值，如果当前值比最大值小，那么将其替换掉即可。

但是似乎还漏了一部分，就是中间留下的那一部分，但能证明这部分肯定不优。
假设当前是第 \(i\) 个，替换掉的是第 \(j(j < i, c_i < c_j)\) 个。
对于当前已经选的数的总和 \(sum\)，有 \(sum + c_i > ix\)。
同时对于 \(k\in (j, i)\) 且没被选的第 \(k\) 个，根据贪心策略肯定有 \(c_k > c_j\)，那么 \(k\) 肯定选不了。
所以不会出现这种情况。

时间复杂度 \(\mathcal{O}(m\log m)\)。

#include<bits/stdc++.h>
inline void Main() {
   int m, x;
   scanf("%d%d", &m, &x);
   int tot = 0, cnt = 0;
   std::priority_queue<int> Q;
   for (int v; m--; tot += x) {
      scanf("%d", &v);
      if (tot >= v)
         tot -= v, cnt++, Q.push(v);
      else if (! Q.empty() && v < Q.top())
         tot += Q.top() - v, Q.pop(), Q.push(v);
   }
   printf("%d\n", cnt);
}
int main() {
   int T;
   scanf("%d", &T);
   while (T--) Main();
   return 0;
}