题目理解

给定 $n$ 条消息，每条消息有两个参数 $a_i$ 和 $b_i$。
阅读一个消息集 $p_1, p_2, \dots, p_k$ 的代价为：

$$\sum_{i=1}^k a_{p_i} + \sum_{i=1}^{k-1} |b_{p_i} - b_{p_{i+1}}| $$

其中消息顺序可以任意排列。用户愿意花费的时间上限为 $l$，要求找出最大的 $k$ 使得存在一个大小为 $k$ 的消息集，其阅读代价 $\le l$。

关键转化

对于任意选定的消息集合 $S$，最优的排列顺序是按 $b$ 值升序（或降序）排列。
因为排序后，相邻 $b$ 的绝对值差之和恰好等于 $b_{\max} - b_{\min}$（中间项正负抵消）。
此时总代价为：

$$\sum_{i \in S} a_i \;+\; \bigl( \max_{i \in S} b_i - \min_{i \in S} b_i \bigr) $$

因此问题转化为：选择一组消息，使得 $a$ 之和 + ($b$ 的最大值减最小值) $\le l$，并最大化消息数量。

算法思路

1. 按 $b$ 排序
   将所有消息按 $b$ 从小到大排序，记排序后的序列为 $(b_1, a_1), (b_2, a_2), \dots, (b_n, a_n)$。

2. 枚举左端点 $l$（最小值位置）
   对于每个左端点 $l$，我们考虑所有右端点 $r \ge l$，此时 $b$ 的范围为 $[b_l, b_r]$，代价中的 $b$ 部分为 $b_r - b_l$。

3. 在区间 $[l, r]$ 内选最优子集
   固定 $b$ 范围后，为了最大化消息数量，应该优先选择 $a$ 值最小的那些消息。
   因此维护一个多重集合（multiset）存储当前区间内所有消息的 $a$ 值，并维护总和 cur。

4. 贪心剔除
   当 cur + (b_r - b_l) > l 时，说明当前选择的所有消息代价超限。此时我们删除当前集合中 $a$ 值最大的一个消息（因为去掉大的 $a$ 能最有效地降低总和，同时只减少一个数量）。重复此操作直到条件满足。

5. 更新答案
   每次满足条件后，当前集合的大小即为在区间 $[l, r]$ 内能选出的最大消息数量。用 ans 记录最大值。

6. 遍历所有 $l, r$
   时间复杂度 $O(n^2 \log n)$，由于 $n \le 2000$ 且 $\sum n^2 \le 4\times 10^6$，完全可行。

代码详解

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

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        int n, L;
        cin >> n >> L;
        vector<pair<int, int>> v(n);   // (b, a)
        for (int i = 0; i < n; i++) {
            cin >> v[i].second >> v[i].first;  // 先读 a，再读 b，存入时交换
        }
        sort(v.begin(), v.end());      // 按 b 升序排序

        int ans = 0;
        for (int l = 0; l < n; l++) {
            multiset<int> s;           // 存储当前区间内的 a 值
            int cur = 0;               // 当前 a 之和
            for (int r = l; r < n; r++) {
                s.insert(v[r].second);
                cur += v[r].second;
                // 当总代价超过 L 时，移除当前集合中最大的 a
                while (!s.empty() && v[r].first - v[l].first + cur > L) {
                    int max_val = *s.rbegin();  // 最大值
                    cur -= max_val;
                    auto it = s.find(max_val); // 找到该值的一个迭代器
                    if (it != s.end()) s.erase(it);
                }
                ans = max(ans, (int)s.size());
            }
        }
        cout << ans << "\n";
    }
    return 0;
}

注意事项

• 排序时 pair 的 first 是 $b$，second 是 $a$，这样 sort 默认按 $b$ 升序。
• 使用 multiset 是因为可能存在相同的 $a$ 值，需要保留多个。
• 删除时使用 find 再 erase 单个元素（C++11 兼容），而非 C++17 的 extract。
• 外层循环枚举左端点，内层枚举右端点，每次内层循环中 while 删除操作的总次数是 $O(n)$，因为每个元素最多被插入和删除一次。

正确性证明

1. 最优顺序性质：对于任意选定集合，按 $b$ 排序后代价最小，因此只需考虑排序后的序列。
2. 固定 $b$ 范围：若最小值在 $l$，最大值在 $r$，则 $b$ 部分代价固定为 $b_r - b_l$。此时问题简化为从 $[l, r]$ 中选若干消息，使 $\sum a$ 尽可能小，从而容纳更多消息。贪心选取最小的 $a$ 是最优的。
3. 贪心剔除：当总和超限时，移除当前最大的 $a$ 是局部最优决策，因为它最大化降低总和的同时只损失一个消息，最终得到的集合一定是该区间内所有可能子集中大小最大的（经典贪心：保留最小 $k$ 个 $a$ 使得总和最小）。
4. 遍历所有区间：枚举所有可能的 $(b_{\min}, b_{\max})$ 对，覆盖了所有选择方案，因此能求得全局最优解。

复杂度分析

• 排序：$O(n \log n)$
• 双重循环：外层 $n$ 次，内层平均 $n$ 次，每次内层操作（插入、删除）为 $O(\log n)$，总复杂度 $O(n^2 \log n)$。
• 由于 $\sum n^2 \le 4\cdot 10^6$，最坏情况下 $n=2000$，$n^2=4\times 10^6$，乘上 $\log 2000 \approx 11$，总操作约 $4.4\times 10^7$，在 3 秒内可接受。