超市促销商品销售计划 - 贪心算法题解

问题分析

超市有 n 件促销商品，每件商品有两个属性：

• 利润 p_i：售出该商品可获得的利润
• 截止时间 d_i：商品必须在时间 d_i 之前完成销售（包含 d_i）

销售约束条件：

1. 每件商品的销售需要恰好 1 个单位时间
2. 同一时间只能销售一件商品
3. 可以选择销售哪些商品以及销售顺序

目标：制定销售计划，使总利润最大化。

算法思路

核心贪心策略

这个问题是经典的 "带截止时间的任务调度问题" 的一个变体。我们需要从 n 个任务（商品）中选择一部分，安排到时间线上，使得：

• 每个任务在其截止时间前完成
• 同一时间只能执行一个任务
• 最大化所选任务的总价值（利润）

关键洞察：从时间轴的末尾向前倒推安排商品销售。

算法流程

1. 数据分组：将所有商品按截止时间分组
2. 倒序处理：从最晚的截止时间开始，向时间 1 推进
3. 选择策略：在每个时间点，选择当前可用的所有商品中利润最大的进行销售

详细算法步骤

1. 数据预处理

// profit[d] 存储所有截止时间为 d 的商品利润
vector<int> profit[N];  // N = 10010，因为 d_i ≤ 10000

// 读入数据并分组
for(int i = 0; i < n; i++){
    scanf("%d%d", &p, &d);
    profit[d].push_back(p);
    max_d = max(max_d, d);  // 记录最晚截止时间
}

2. 倒序安排销售

priority_queue<int> pq;  // 最大堆，存储当前可选的商品利润
int best = 0;  // 最大总利润

// 从最晚的时间开始，倒着处理每个时间点
for(int time = max_d; time >= 1; time--){
    // 将所有截止时间等于当前时间的商品加入候选集
    for(int i = 0; i < profit[time].size(); i++){
        pq.push(profit[time][i]);
    }
    
    // 如果当前时间点有候选商品，选择利润最大的销售
    if(!pq.empty()){
        best += pq.top();  // 选择最大利润的商品
        pq.pop();          // 该商品已被安排
    }
}

算法逻辑解释

假设当前处理的时间点是 t：

• 优先队列 pq 中包含所有截止时间 ≥ t 且尚未被安排的商品
• 这些商品都可以安排在时间 t 或之后销售
• 选择其中利润最大的商品在时间 t 销售是最优的
• 剩余商品可以安排在更早的时间（如果它们的截止时间允许）

正确性证明

引理1：倒序处理的优势

从后往前处理时间轴确保了：

1. 早期时间有更多选择：当处理时间 t 时，我们已经看到了所有截止时间 ≥ t 的商品
2. 不会错过高利润商品：高利润商品即使截止时间较早，也有机会被安排

引理2：贪心选择的最优性

假设在某个时间点 t，当前可选的商品集合为 C。选择 C 中利润最大的商品 g_max 安排在时间 t 不会导致次优解。

证明（交换论证）： 假设存在一个更优的安排，在时间 t 安排了商品 g（g ≠ g_max，且 profit(g) < profit(g_max)）。 我们可以交换 g_max 和 g 的安排：

• 如果 g_max 在原安排中在时间 t' > t，交换后 g_max 在时间 t（合法，因为 d_{g_max} ≥ t）
• g 被安排到时间 t'（也合法，因为 d_g ≥ t，且 t' > t）

交换后总利润增加，因此原安排不是最优的。

定理：算法得到最优解

通过数学归纳法可以证明：对于每个时间点 t，算法的选择都是当前情况下的最优选择，且这些局部最优选择构成了全局最优解。

时间复杂度分析

• 分组存储：O(n)，n ≤ 10000
• 优先队列操作：
  • 每个商品最多入队一次：O(log n)
  • 每个时间点最多出队一次：O(log n)
• 总时间复杂度：O(n log n)

在题目数据范围（n ≤ 10000）内，这个复杂度完全可接受。

空间复杂度分析

• 分组数组：O(N)，N = 10010
• 优先队列：最坏情况下 O(n)
• 总空间复杂度：O(n)

示例分析

示例1（题目中的例子）

输入：4  50 2  10 1  20 2  30 1

商品列表：
- 商品A: 利润50, 截止时间2
- 商品B: 利润10, 截止时间1
- 商品C: 利润20, 截止时间2
- 商品D: 利润30, 截止时间1

分组：
profit[1] = {10, 30}
profit[2] = {50, 20}

执行过程：
时间2：候选集 {50, 20} → 选50，利润=50
时间1：候选集 {10, 30, 20} → 选30，利润=30
总利润：80

示例2

输入：7  20 1  2 1  10 3  100 2  8 2  5 20  50 10

分组（简化）：
profit[1] = {20, 2}
profit[2] = {100, 8}
profit[3] = {10}
profit[10] = {50}
profit[20] = {5}

执行过程（关键步骤）：
时间20：选5
时间19-11：无候选
时间10：选50
时间9-4：无候选
时间3：选10
时间2：选100
时间1：选20
总利润：5+50+10+100+20=185

算法特点

1. 为什么使用优先队列（最大堆）？

• 需要快速找到当前候选商品中利润最大的
• 优先队列（最大堆）支持 O(1) 时间获取最大值，O(log n) 时间插入和删除

2. 为什么从后往前处理？

• 确保每个时间点都能看到所有符合条件的商品
• 避免高利润商品因为截止时间较早而被忽略

3. 算法的巧妙之处

• 不需要显式地跟踪时间占用情况
• 通过倒序处理自然保证了时间冲突的避免
• 分组存储简化了数据组织

实现细节

边界情况处理

1. n = 0：直接输出 0
2. 所有商品截止时间相同：算法仍然正确
3. 利润相同，截止时间不同：算法会优先安排截止时间较晚的（因为先看到它们）

代码优化

原代码中的 profit[N] 使用 vector 数组，可以动态调整大小，避免内存浪费。每次测试用例开始前需要清空数组。

总结

本问题通过倒序贪心算法高效解决：

1. 分组存储：按截止时间组织商品
2. 倒序处理：从最晚时间向最早时间推进
3. 贪心选择：每个时间点选择当前可用的最大利润商品
4. 优先队列：高效管理候选商品

算法保证了最优解，时间复杂度 O(n log n)，空间复杂度 O(n)，能够高效处理最大规模的数据。这种"从后往前+最大堆"的策略是解决带截止时间调度问题的经典方法，广泛应用于任务调度、资源分配等领域。

解题思路分析

核心思想

采用贪心算法求解。其核心思路是从最大截止时间开始，依次考虑每个截止时间的商品利润。在每个截止时间，优先选择利润最大的商品进行销售，这样能保证在满足截止时间的前提下，尽可能获取最大利润。

算法正确性证明

假设存在一种更优的销售计划，其选择的商品与当前贪心算法选择的商品不同。由于优先选择利润大的商品，对于任何截止时间d，如果在当前贪心算法中没有选择某个利润较小的商品，而在所谓更优的计划中选择了它，那么在当前截止时间内，将这个利润较小的商品替换为贪心算法选择的利润最大的商品，只会使总利润增加或保持不变。因为截止时间的限制，在同一截止时间内，选择利润更大的商品总是更优的策略。 对于不同截止时间的商品选择，从大截止时间到小截止时间依次考虑，能确保在满足所有截止时间的情况下，最大程度地积累利润。例如，如果有两个商品A（利润pA，截止时间dA）和B（利润pB，截止时间dB，dA > dB），先考虑dA，选择A不会影响在dB时对商品的选择，且能保证先获取较大的利润。

时间复杂度和空间复杂度分析

时间复杂度

输入部分：读取n个商品的数据，时间复杂度为$O(n)$。 计算最优利润部分：对于每个截止时间d（最多有max_d个不同的截止时间），将其对应的利润值压入优先队列，每个截止时间内处理利润值的时间复杂度为$O(k)$（k为该截止时间下商品的数量），总的时间复杂度为$O(max_d \times k)$，但由于所有商品数量为n，所以这部分时间复杂度也可近似看作$O(n)$。因此，整体时间复杂度为$O(n)$。

空间复杂度

存储利润的向量数组profit[N]，最多存储n个利润值，空间复杂度为$O(n)$。 优先队列pq中最多存储n个元素，空间复杂度为$O(n)$。所以，总的空间复杂度为$O(n)$。

总结

通过合理的数据结构和贪心算法，有效地解决了寻找最优销售计划利润的问题。其从输入数据的处理、利润计算到结果输出，逻辑清晰，时间复杂度和空间复杂度都能满足题目要求。代码如下：

#include <iostream>
#include <vector>
#include <stdio.h>
#include <utility>
#include <queue>
#include <stack>
#include <algorithm>
#include <set>
using namespace std;
const int N = 10010;
int n;
vector<int> profit[N];
int main(){
    while(scanf("%d",&n)!=EOF){
        int max_d = 0;
        int p,d;
        for(int i=0;i<N;i++)
            profit[i].clear();
        for(int i=0;i<n;i++){
            scanf("%d%d",&p,&d);
            profit[d].push_back(p);
            max_d = max(max_d,d);
        }
        priority_queue<int> pq;
        int best = 0;
        for(d=max_d;d>=1;d--){
            for(int i=0;i<profit[d].size();i++){
                pq.push(profit[d][i]);
            }
            if(pq.empty()) continue;
            best += pq.top();
            pq.pop();
        }
        printf("%d\n",best);
    }
}