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

Myth丶恋晨 2022-06-12 12:16 128阅读 0赞

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

[vjudge题目链接][vjudge]

[建议参考博客—题意分析][Link 1]

以下为Accepted代码

#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("%d\n", 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];
        }
    }

[vjudge]: https://vjudge.net/contest/163007#problem/G
[Link 1]: http://www.cnblogs.com/liuxin13/p/4669327.html