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

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

vjudge题目链接

建议参考博客—题意分析

以下为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("%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];
    }
}

最后

以上就是可靠冬瓜为你收集整理的G - Supermarket ——贪心+并查集优化时间复杂度的全部内容，希望文章能够帮你解决G - Supermarket ——贪心+并查集优化时间复杂度所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。