题目大意

题目链接

超市里有N个商品. 第i个商品必须在保质期(第di天)之前卖掉, 若卖掉可让超市获得pi的利润.
每天只能卖一个商品.
现在你要让超市获得最大的利润.

分析

用并查集向前查找， 太妙了呀。

首先贪心， 价值越大的物品， 越放在快过期的那天卖最好， 因为你肯定要卖的嘛， 如果快过期那天已经卖了别的了， 就说明有更大价值东西在那天卖了。

然后寻找最靠近保质期切没有被用到的哪一天 ， 这不就是并查集？

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <cstdio>
#include <utility>
#include <iostream>
#include <algorithm>

using namespace std;
#define ms(a, b) memset((a), (b), sizeof(a))
typedef long long ll;
const int N = 1e4 + 5;

inline ll read() {
    ll res = 0;bool f = 0;char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = 1;ch = getchar();}
    while (ch <= '9' && ch >= '0') {res = (res << 3) + (res << 1) + ch - '0';ch = getchar();}
    return f ? (~res + 1) : res;
}
int f[N];
int tofind(int x){
    if (f[x] != x) f[x] = tofind(f[x]);
    return f[x];
}
struct node{
    int p, d;
}a[N];
bool cmp(node x, node y){
    if (x.p != y.p) return x.p > y.p;
    return x.d < y.d;
}
int main(){
    int n;
    while(cin >> n){
        for (int i = 0; i < n; ++i) a[i].p = read(), a[i].d = read();
        for (int i = 0; i < N; ++i) f[i] = i;
        sort(a, a + n, cmp);
        ll ans = 0;
        for (int i = 0; i < n; ++i){
            int fa = tofind(a[i].d);
            if (fa < 1) continue;
            ans += a[i].p;
            f[fa] = fa - 1;
        }
        cout << ans << "\n";
    }
    return 0;
}
恰似你一低头的温柔，较弱水莲花不胜寒风的娇羞， 我的心为你悸动不休。  --mingfuyan

千万不要图快——如果没有足够的时间用来实践， 那么学得快， 忘得也快。