Supermarket---poj456（贪心并查集优化）

题意是现有n个物品，每个物品有一个保质期和一个利润，现在每天只能卖一个商品，问最大的利润是多少，商品如果过期了就不能卖了；

暴力的方法：

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <stack>

#include <queue>

#include <map>

#include <vector>

using namespace std;

typedef long long LL;

#define PI 4*atan(1.0)

#define N 10550

#define met(a, b) memset(a, b, sizeof(a))

struct node

{

    int p, d;

}a[N];

int cmp(node p, node q)

{

    if(p.p != q.p)

        return p.p > q.p;

    return p.d > q.d;

}

int vis[N];

int main()

{

    int n;

    while(scanf("%d", &n)!=EOF)

    {

        met(vis, );

        met(a, );

        for(int i=; i<=n; i++)

            scanf("%d %d", &a[i].p, &a[i].d);

        sort(a+, a+n+, cmp);

        int ans = ;

        for(int i=; i<=n; i++)

        {

            for(int j=a[i].d; j>=; j--)

            {

                if(!vis[j])

                {

                    ans+=a[i].p;

                    vis[j] = ;

                    break;

                }

            }

        }

        printf("%d\n", ans);

    }

    return ;

}

并查集优化：

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <stack>

#include <queue>

#include <map>

#include <vector>

using namespace std;

typedef long long LL;

#define PI 4*atan(1.0)

#define N 10500

#define met(a, b) memset(a, b, sizeof(a))

struct node

{

    int p, d;

}a[N];

int cmp(node p, node q)

{

    if(p.p != q.p)

        return p.p > q.p;

    return p.d > q.d;

}

int f[N];

int Find(int x)

{

    if(f[x]!=x)

        f[x] = Find(f[x]);

    return f[x];

}

int main()

{

    int n;

    while(scanf("%d", &n)!=EOF)

    {

        for(int i=; i<N; i++)

            f[i] = i;

        met(a, );

        for(int i=; i<=n; i++)

            scanf("%d %d", &a[i].p, &a[i].d);

        sort(a+, a+n+, cmp);

        int ans = ;

        for(int i=; i<=n; i++)

        {

            int t = Find(a[i].d);

            if(t > )

            {

                ans += a[i].p;

                f[t] = t-;

            }

        }

        printf("%d\n", ans);

    }

    return ;

}