Supermarket

题目解析

这道题是典型的带时限的调度问题，目标是在满足每个任务截止日期的前提下，最大化总利润。每个任务耗时一天。

我们很自然地能想到贪心策略。但是应该以什么为标准进行贪心呢？

按截止日期从小到大？ 这样似乎可以优先处理紧急的任务，但可能会因为先做了利润很低但紧急的任务，而错过了利润更高但时限更宽裕的任务。
按利润从大到小？ 这个看起来更靠谱。我们总是优先选择能带来最大收益的商品。

我们来深入探讨第二种思路：优先处理利润最高的商品。

对于一个利润最高的商品，我们应该在哪一天卖掉它？直觉上，应该在离它截止日期尽可能近的那天卖掉，以便给其他商品留出更多的时间窗口。

例如，一个商品利润 100，截止日期是第 3 天。我们应该在第 3 天卖掉它。如果第 3 天已经被占用了，我们就尝试第 2 天，再不行就尝试第 1 天。如果从第 3 天到第 1 天都被占用了，那这个商品就只能放弃。

这个策略“听起来”是正确的，但每次为商品寻找可用日期时，从截止日期开始往前逐一检查，效率太低。在最坏情况下（例如所有商品截止日期都很大），时间复杂度会达到 $O(N \times D)$ ，其中 D 是最大天数，这会超时。

我们需要一个高效的方法来“查找并占用”一个可用的时间点。这正是并查集大显身手的地方。

解法一：贪心 + 并查集

核心思路

贪心策略：将所有商品按利润从大到小排序。
遍历商品：依次处理每个高利润商品。
寻找可用天：对于当前商品，在其截止日期 d 内，为它寻找一个可用的、最晚的一天。
优化查找：使用并查集来快速找到这个“最晚可用天”。

并查集的巧妙应用

我们可以把从 1 到最大天数 max_d 的每一天看作一个节点。并查集 fa[i] 的含义是：第 i 天或在它之前（小于等于 i）的那个最晚的可用日期。

初始化：fa[i] = i，表示第 i 天就是它自己，代表这一天当前是可用的。
查找 find(d)：当我们为截止日期为 d 的商品寻找可用天时，我们调用 find(d)。
- 如果 find(d) 返回 r > 0，说明找到了一个可用的日期 r。
- 如果 find(d) 返回 0，说明从 d 到 1 的所有日期都已被占用。
占用 union：当我们占用了第 r 天后，这一天就变得不可用了。下次再有商品想找第 r 天时，我们应该直接告诉它去 r-1 找。所以，我们执行合并操作：fa[r] = r - 1。

这样，通过路径压缩，下一次 find(r) 会直接跳到 r-1 的根节点，实现了快速查找前一个可用日期的目的。

C++ 代码实现

cpp

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 商品结构体
struct Item {
    int p; // 利润 (profit)
    int d; // 截止日期 (deadline)
};

// 比较函数：按利润从大到小排序
bool compare(const Item &a, const Item &b) {
    return a.p > b.p;
}

const int MAX_DAY = 10005; 
int fa[MAX_DAY]; // 并查集数组, fa[i] 表示 <= i 的最近可用空闲日子

// 并查集查找函数（带路径压缩）
// 作用：找到第 x 天对应的“最近可用空闲日子”
int find(int x) {
    if (fa[x] == x) return x;
    return fa[x] = find(fa[x]); // 路径压缩，直接连到根节点
}

void solve() {
    int n;
    // 处理多组输入 (UVa 题目常见格式)
    while (cin >> n) {
        vector<Item> items(n);
        int max_d = 0; // 记录题目中出现的最大天数，用于初始化并查集

        for (int i = 0; i < n; ++i) {
            cin >> items[i].p >> items[i].d;
            max_d = max(max_d, items[i].d);
        }

        // 1. 贪心策略第一步：按利润从大到小排序
        sort(items.begin(), items.end(), compare);

        // 2. 初始化并查集
        // 刚开始每一天都是独立的，fa[i] 指向自己，表示第 i 天是可用的
        for (int i = 0; i <= max_d + 1; ++i) { // 多初始化一位，避免边界问题
            fa[i] = i;
        }

        long long total_profit = 0;

        // 3. 遍历每个商品
        for (int i = 0; i < n; ++i) {
            // 查找该商品截止日期 d 对应的可用日子
            // find(d) 会返回 <= d 的最大的空闲日子
            int available_day = find(items[i].d);

            // 如果找到的日子 > 0，说明在截止日期前有空位
            if (available_day > 0) {
                total_profit += items[i].p;

                // 关键操作：占用这一天
                // 将 available_day 的父节点指向 available_day - 1
                // 这样下次再查 available_day 时，就会自动跳到左边去找空位
                fa[available_day] = find(available_day - 1); 
            }
            // else: available_day == 0，说明从 1 到 d 全满了，该商品只能丢弃
        }

        cout << total_profit << endl;
    }
}

int main() {
    // 优化 I/O 速度
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    return 0;
}

复杂度分析：排序的复杂度是 $O(N \log N)$ ，之后遍历 N 个商品，每次并查集操作的平均复杂度接近 $O(\alpha(D))$ ，其中 $\alpha$ 是反阿克曼函数，增长极其缓慢，可近似为常数。所以总复杂度为 $O(N \log N)$ 。

解法二：反悔贪心 + 优先队列

还有一种非常巧妙的思路，称为“反悔贪心”。

核心思路

这次我们换一个贪心策略：将所有商品按截止日期从小到大排序。这样做的好处是，当我们处理到第 i 天时，我们只需要考虑截止日期不晚于 i 的商品，而不用担心未来的商品。

我们维护一个“购物车”（用最小堆/优先队列实现），里面存放我们当前决定要卖的商品。

排序：将所有商品按截止日期 d 从小到大排序。
遍历商品：依次遍历排序后的商品。假设当前商品的截止日期为 d，利润为 p。
决策：
- 如果当前购物车的商品数量小于 d，说明在 d 天之内还有空闲的日子，我们可以直接把当前商品加入购物车。
- 如果当前购物车的商品数量等于 d，说明从第 1 天到第 d 天都已经排满了。此时，我们面临选择：要不要为了这个新商品而放弃一个已选的？
  - 查看购物车里利润最低的商品（也就是小顶堆的堆顶）。
  - 如果当前商品的利润 p 大于购物车里利润最低的商品，那么进行“反悔”操作：扔掉那个利润最低的，把当前这个利润更高的加进去。这样总利润更高，且总任务数不变，依然是 d 个，所以一定能安排在 d 天之内。
  - 如果当前商品利润更低，那就不做任何操作，直接放弃当前商品。

为什么这个策略是正确的？（交换论证）

当我们决定用一个利润更高的新商品 X 替换掉购物车里利润最低的旧商品 Y 时，为什么方案仍然是合法的？

我们是按截止日期 d 从小到大处理的，所以新商品 X 的截止日期 $d_X$ 一定不小于购物车内任何商品（包括 Y）的截止日期，即 $d_X \ge d_Y$ 。
原方案中，购物车里的 k 个商品能在 k 天内完成。现在我们用 X 替换 Y。
由于 $d_X \ge d_Y$ ，任何原先可以安排 Y 的时间点，也一定可以安排 X。所以，新选出的 k 个商品也一定能在 k 天内完成。
这个替换操作保证了在任何时刻，我们的选择都是当前最优的，并且总能满足时限要求。

C++ 代码实现

cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

struct Item {
    int p, d;
};

bool compareItems(const Item& a, const Item& b) {
    return a.d < b.d;
}

void solve() {
    int n;
    while (cin >> n) {
        vector<Item> items(n);
        for (int i = 0; i < n; ++i) {
            cin >> items[i].p >> items[i].d;
        }

        // 1. 按截止日期从小到大排序
        sort(items.begin(), items.end(), compareItems);

        // 2. 最小堆作为“购物车”，存放已选商品的利润
        priority_queue<int, vector<int>, greater<int>> cart;
        
        // 3. 遍历所有商品
        for (int i = 0; i < n; ++i) {
            if (cart.size() < items[i].d) {
                // 情况1：天数有富余，直接将商品加入购物车
                cart.push(items[i].p);
            } else { 
                // 情况2：天数已满，考虑是否“反悔”
                // 如果当前商品利润 > 购物车中利润最小的商品
                if (items[i].p > cart.top()) {
                    cart.pop(); // 扔掉利润最小的
                    cart.push(items[i].p); // 加入当前这个利润更高的
                }
            }
        }

        long long total_profit = 0;
        while (!cart.empty()) {
            total_profit += cart.top();
            cart.pop();
        }
        cout << total_profit << endl;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    return 0;
}

复杂度分析：排序的复杂度是 $O(N \log N)$ 。遍历 N 个商品，每次对优先队列（大小最多为 N）进行操作，复杂度为 $O(\log N)$ 。所以总复杂度也是 $O(N \log N)$ 。

两种解法对比

特性	贪心 + 并查集	反悔贪心 + 优先队列
排序依据	利润 (Profit) 从大到小	截止日期 (Deadline) 从小到大
核心思想	为高价值的商品优先寻找并抢占最晚的时间点。	逐步构建最优解，若遇到更优选择则“反悔”。
数据结构	并查集 (Disjoint Set Union)	优先队列 (Priority Queue / Min-Heap)
复杂度	$O(N \log N)$	$O(N \log N)$
优点	思路直观，对应“抢占时间槽”的物理过程。	是“反悔贪心”的经典模板，适用性更广。

两种方法都能高效地解决本问题，理解它们有助于我们从不同角度思考贪心算法的设计。

总结

一个物品有两个属性,为了避免同时考虑两个属性,我们选择对一个属性进行排序 (单调性总是帮我们节省思考难度)

对于利润排序 坑位填充 -> 并查集
对于时间排序 集合更新 -> 替换最不好的值

目录

题目解析

解法一：贪心 + 并查集

核心思路

并查集的巧妙应用

C++ 代码实现

解法二：反悔贪心 + 优先队列

核心思路

为什么这个策略是正确的？（交换论证）

C++ 代码实现

两种解法对比

总结