解题思路分析

核心思想

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

算法正确性证明

假设存在一种更优的销售计划，其选择的商品与当前贪心算法选择的商品不同。由于优先选择利润大的商品，对于任何截止时间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);
    }
}