题意理解

我们有 n 个物品，每个物品有：

• 重量 w
• 截止时间 d（必须在第 d 秒前购买）
• 购买一个物品需要 1 秒

我们要选择一些物品，使得可以按某种顺序在截止时间前购买。

方案比较规则：

1. 买的物品数量多的更好
2. 数量相同时，总重量小的更好

输出前 k 个最好的方案。

---

关键点

一个物品集合可行的条件是：如果我们买了 m 个物品，那么它们的截止时间必须足够大，能够安排在第 1 到 m 秒购买。

具体来说：将选中的物品按截止时间从小到大排序后，第 i 个物品的截止时间必须 ≥ i。

---

思路

我们可以用动态规划来解决：

1. 先把所有物品按截止时间 d 从小到大排序
2. 用 dp[j] 表示选 j 个物品的最小总重量
3. 遍历每个物品，更新 dp 数组
4. 最后收集所有可能的 (数量, 重量) 对，按题目要求排序，输出前 k 个

---

算法步骤

1. 读入 n, k 和物品列表
2. 按 d 从小到大排序物品
3. 初始化 dp 数组，dp[0] = 0，其他为无穷大
4. 对于每个物品 (w, d)：
   • 从后往前更新 dp 数组（避免重复选择）
   • 对于 j 从 n 到 1：
     • 如果 j ≤ d 且 dp[j-1] 不是无穷大：
       • dp[j] = min(dp[j], dp[j-1] + w)
5. 收集所有 dp[j] 不是无穷大的 (j, dp[j]) 对
6. 按数量从大到小、重量从小到大排序
7. 输出前 k 个，不足补 (0, 0)

---

代码实现

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    
    vector<pair<int, int>> items(n); // (d, w)
    for (int i = 0; i < n; i++) {
        cin >> items[i].second >> items[i].first;
    }
    
    // 按截止时间排序
    sort(items.begin(), items.end());
    
    // dp[j] = 选j个物品的最小总重量
    vector<long long> dp(n + 1, LLONG_MAX);
    dp[0] = 0;
    
    for (int i = 0; i < n; i++) {
        int w = items[i].second;
        int d = items[i].first;
        // 从后往前更新
        for (int j = n; j >= 1; j--) {
            if (dp[j - 1] != LLONG_MAX && j <= d) {
                if (dp[j] > dp[j - 1] + w) {
                    dp[j] = dp[j - 1] + w;
                }
            }
        }
    }
    
    // 收集所有方案
    vector<pair<int, long long>> solutions;
    for (int j = n; j >= 0; j--) {
        if (dp[j] != LLONG_MAX) {
            solutions.push_back({j, dp[j]});
        }
    }
    
    // 排序：数量多的在前，数量相同时重量小的在前
    sort(solutions.begin(), solutions.end(), [](auto& a, auto& b) {
        if (a.first != b.first) return a.first > b.first;
        return a.second < b.second;
    });
    
    // 输出前k个
    for (int i = 0; i < k; i++) {
        if (i < solutions.size()) {
            cout << solutions[i].first << " " << solutions[i].second << "\n";
        } else {
            cout << "0 0\n";
        }
    }
    
    return 0;
}

---

样例验证

样例1

输入：

3 1
1 1
1 1
1 3

输出：

2 2

解释：最多能买2个物品，最小重量是2。

样例2

输入：

4 3
1 1
10 1
2 3
10 3

输出：

3 13
3 22
2 3

解释：

• 买3个物品的最小重量是13（物品1,3,4）
• 买3个物品的次小重量是22（物品2,3,4）
• 买2个物品的最小重量是3（物品1,3）

样例3

输入：

2 4
1 1
2 2

输出：

2 3
1 1
1 2
0 0

解释：

• 买2个物品：重量3
• 买1个物品：重量1或2
• 买0个物品：重量0

---

复杂度分析

• 排序：O(n log n)
• DP：O(n²)
• 总复杂度：O(n²)，对 n ≤ 2000 可行

这个解法能够正确求出前 k 个最优方案。