题目解析

我们有一个回收中心，初始有 $n$ 个垃圾袋，第 $i$ 个重量为 $a_i$。每秒先选一个袋子销毁，若其重量 严格大于 $c$ 则花费 $1$ 硬币，否则免费；然后所有剩余袋子的重量翻倍。

定义：若 $a_i \le c$ 称为 免费袋，否则称为 昂贵袋。

关键观察

1. 只要还有免费袋，就应该销毁免费袋（因为免费的不花钱，而昂贵袋迟早要花 $1$ 硬币，推迟销毁不会增加代价）。
2. 销毁一个免费袋后，所有剩余袋子的重量都会翻倍。因此，一个原本免费的袋子可能在未来变得昂贵。
3. 应该优先销毁当前重量最大的免费袋。因为大的袋子在翻倍后更容易超过 $c$，留给它的“免费时间窗口”更短。

最优策略

设当前已经免费销毁了 $k$ 个袋子，则当前所有剩余袋子的重量已经乘以了 $2^k$（因为每销毁一个免费袋，其余袋子翻倍一次）。
对于初始免费袋中某个重量为 $a$ 的袋子，在它被销毁的时刻，其实际重量为 $a \times 2^{k}$（$k$ 是它之前免费销毁的袋子个数）。

因此，我们可以：

• 将所有初始免费袋（$a_i \le c$）单独取出，按重量 降序 排序。
• 依次处理每个免费袋：
  设当前已经成功免费销毁了 $cnt$ 个袋子，当前倍增因子为 $2^{cnt}$。
  若 $a_i \times 2^{cnt} \le c$，则它可以免费销毁，令 $cnt = cnt + 1$；
  否则，它已变为昂贵袋，不再免费，跳过（$cnt$ 不变），继续处理下一个免费袋（因为它仍可能免费，但需要乘以相同的 $2^{cnt}$）。
• 处理完所有免费袋后，剩余的袋子（包括初始昂贵袋和那些变成昂贵的免费袋）每个都必须花 $1$ 硬币销毁。
• 总花费 = 剩余袋子数 = $n - cnt$。

正确性说明

• 贪心选择当前最大的免费袋是最优的：如果某个较大的袋子被推迟，它可能很快变得昂贵，从而失去一次免费机会；而较小的袋子推迟后仍可能免费。
• 由于免费销毁不改变后续昂贵袋的最终代价（每个昂贵袋始终花费 $1$），最大化免费销毁的数量等价于最小化总花费。

算法步骤

对于每个测试用例：

1. 读入 $n, c$ 和数组 $a$。
2. 收集所有 $a_i \le c$ 的值到列表 free。
3. 将 free 按降序排序。
4. 初始化 $cnt = 0$。
5. 遍历 free 中的每个重量 $w$：
   • 若 $w \times (1 \ll cnt) \le c$，则 $cnt = cnt + 1$。
   • 否则，什么也不做（跳过）。
6. 输出 $n - cnt$。

时间复杂度：排序 $O(n \log n)$，遍历 $O(n)$，总 $O(n \log n)$，满足 $n \le 30, t \le 1000$。

代码实现（C++）

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

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n; ll c;
        cin >> n >> c;
        vector<ll> a(n);
        vector<ll> free;
        for (int i = 0; i < n; ++i) {
            cin >> a[i];
            if (a[i] <= c) free.push_back(a[i]);
        }
        sort(free.rbegin(), free.rend()); // 降序
        int cnt = 0;
        for (ll w : free) {
            if (w * (1LL << cnt) <= c) {
                ++cnt;
            }
        }
        cout << n - cnt << '\n';
    }
    return 0;
}

示例验证

以第一个测试用例为例：
$n=5, c=10$，$a=[10,4,15,1,8]$
初始免费袋：$[10,4,1,8]$，降序 $[10,8,4,1]$

• $cnt=0$：$10\times1=10 \le 10$ → $cnt=1$
• $cnt=1$：$8\times2=16 >10$ → 跳过
• $cnt=1$：$4\times2=8 \le 10$ → $cnt=2$
• $cnt=2$：$1\times4=4 \le 10$ → $cnt=3$
  最终 $cnt=3$，答案 $5-3=2$，与输出一致。