G - Supermarket ——贪心+并查集优化时间复杂度

180 阅读 0 评论 119 点赞

我是靠谱客的博主可靠冬瓜，这篇文章主要介绍G - Supermarket ——贪心+并查集优化时间复杂度，现在分享给大家，希望可以做个参考。

Think:
1知识点：贪心+并查集优化时间复杂度
2题意分析：给定n个商品的价值和售卖截止时间，每天可售卖一个商品，询问可获得的最大利润
3解题思路：贪心思想取当前时间的最优解，暴力n*n基本超时，进而并查集优化时间复杂度
4反思：独立思考，不要一味依赖解题报告，好的思想和方法可以借鉴，但一定要有自己的思考和创新点，多思考，多反思

vjudge题目链接

建议参考博客—题意分析

以下为Accepted代码

复制代码

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
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e4 + 4;

struct node {
    int p;
    int d;
}book[N];

bool cmp(struct node a, struct node b){
    if(a.p != b.p)
        return (a.p > b.p);/*价值降序*/
    else
        return (a.d < b.d);/*日期升序*/
}

int n, f[N];

void Init();
int get_f(int x);

int main(){
    int i, ans, t;
    while(~scanf("%d", &n)){
        ans = 0;
        Init();

        for(i = 1; i <= n; i++){
            scanf("%d %d", &book[i].p, &book[i].d);
        }
        sort(book+1, book+n+1, cmp);

        for(i = 1; i <= n; i++){
            t = get_f(book[i].d);
            if(t != 0){
                ans += book[i].p;
                f[t] = t-1;
            }
        }

        printf("%dn", ans);
    }
    return 0;
}
void Init(){
    for(int i = 1; i <= N; i++)
        f[i] = i;
}
int get_f(int x){
    if(f[x] == x)
        return f[x];
    else {
        f[x] = get_f(f[x]);
        return f[x];
    }
}