题目

一家超市出售一套产品 。在截止期限 内，它为每种产品 赚取利润 ，该期限是从开始销售​​之时起以时间单位的整数表示的。每种产品仅花费一个时间单位就可以出售。
销售进度表 是产品 的有序子集，根据 的顺序，每个产品 的销售在截止期限 之前或 到期时完成。
销售计划的利润为 。最佳销售时间表是利润最高的时间表。

编写一个程序，该程序从输入文本文件中读取产品集，并为每组产品计算最佳销售计划的利润。

解题思路

直接使用贪心算法

将产品按照利润从大到小进行排序，优先售卖利润高的产品。
遍历产品，对于每个产品 ，它可以选择在第 1 到第 个时间单位售卖。
而对于每个产品，越晚卖越好，这样可以卖更多的其他截止日期更小的产品。
所以，优先在第 个时间单位卖产品 ，
如果这个时间单位已卖过其他产品（），就选第 天卖，依此类推。

C++代码

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

struct Prod{
    int p;
    int d;
};

bool cmp(Prod& x, Prod& y){
    return x.p > y.p;
}

int main(){
    int n;
    while(cin >> n){
        vector<Prod> a(n);
        int deadline = 0;
        for(int i=0; i<n; ++i){
            cin >> a[i].p >> a[i].d;
            deadline = max(deadline, a[i].d);
        }
        sort(a.begin(), a.end(), cmp);
        vector<bool> vis(deadline+1, false);
        int ans = 0;
        for(int i=0; i<a.size(); ++i){
            int k = a[i].d;
            while(k>=1 && vis[k]) --k;
            if(k>=1){
                ans += a[i].p;
                vis[k] = true;
            }
        }
        cout << ans << endl;
    }
}