POJ 1456 Supermarket(贪心+并查集)

Description

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

链接： http://poj.org/problem?id=1456

Analyze

最主要的是贪心思想：

保质期长的商品早卖晚卖对自身无影响，但保质期短的商品却必须早卖

如此一来，贪心体现在：当前选中的最贵的商品最大限度地晚卖

若当前最贵的在保质期内：

若保质期的最后一天未被标记，则在那一天卖掉它，标记这一天

若保质期的最后一天标记了(卖了别的商品)，那就在前一天卖掉它，不行再往前推一天，总之(在保质期内)越晚越好

Code

#include <set>
#include <map>
#include <stack>
#include <queue>
#include <ctime>
#include <cmath>
#include <cstdio>
#include <vector>
#include <bitset>
#include <string>
#include <cstring>
#include <sstream>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <functional>
#define eps 1e-8
#define PI acos(-1.0)
#define ll long long
using namespace std;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
#define Close ios::sync_with_stdio(false);

void Debug(char * s)
{
    cout << "-------------  " << s << "  -------------" << '\n';
}

typedef pair<int, int> P;
bool cmp(P a, P b)
{
    return a.first > b.first;
}

int pre[10005];
int found(int x)
{
    if(pre[x] == -1)
        return x;
    return pre[x] = found(pre[x]);
}

int main()
{
    int n;
    while(~scanf("%d", &n))
    {
        memset(pre, -1, sizeof(pre));
        int price, day;
        vector<P> vec;
        for(int i = 0; i < n; ++i)
        {
            scanf("%d%d", &price, &day);
            vec.push_back(P(price, day));
        }
        sort(vec.begin(), vec.end(), cmp);
        ll ans = 0;
        for(int i = 0; i < n; ++i)
        {
            int num = found(vec[i].second);
            if(num > 0)
            {
                ans += vec[i].first;
                pre[num] = num - 1;
            }
        }
        cout << ans << '\n';
    }
    return 0;
}
Copy
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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

found函数压缩的过程是标记的过程