145. 超市

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

using namespace std;

#define PII pair<int, int>
#define x first
#define y second

const int N = 10010;

int p[N];
int n;
vector<PII> v;

/*
    贪心策略：
    对于每一件商品，在尽量晚的时间卖出，并且优先卖出利润高的
    对于一件商品{p, d}, find(d)可以得到这件商品能够被卖出的最晚时间
    由于商品已经按照利润降序排序，所以可以实现优先卖出利润高的，
    并且对于每一件商品尽量晚一些卖出
*/

int find(int x){
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main(){
    while(cin >> n){
        
        v.clear();
        
        while(n --){
            int p, b;
            
            cin >> p >> b;
            v.push_back({p, b});
        }
        
        sort(v.rbegin(), v.rend()); // 按第一关键字利润降序
        
        for(int i = 1; i <= 10000; i ++) p[i] = i;
        
        int res = 0;
        
        for(auto t : v)
            if(find(t.y)){
                res += t.x;
                p[find(t.y)] = p[find(t.y) - 1]; // 原本天数为t.y的商品的最晚能够卖出的时间应该减一，因为t.y这天已经选择了要卖出的商品
            }
    
        cout << res << endl;
    }
    
    return 0;
}

145. 超市

原文：https://www.cnblogs.com/tomori/p/13890325.html