supermarket

题意：给你n个商品，商品的利润和商品的过期时间，商品必须在过期时间内卖才能算利润，每天只能卖一件商品，问利润最大值。

思路：用并查集+贪心的思路，先给商品从大到小排序，然后选择过期时间的根节点，再将根节点和根节点-1的时间merge，当根节点不为0，累计加上利润

最后求得最大值。因为过期时间具有传递性，你在第n天卖等价于第n-1天卖，很容易证得思路的正确性。

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<vector>

#include<map>

#include<queue>

#include<cmath>

#define ll long long

using namespace std;

struct point

{

    int x;

    int y;

}a[];

int fa[];

bool cmp(point a,point b)

{

    return a.x>b.x;

}

int get(int k)

{

    return fa[k]==k?k:fa[k]=get(fa[k]);

}

void merge(int x,int y)

{

    fa[get(x)]=get(y);

}

int main()

{

    int n;

    while(~scanf("%d",&n))

    {

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

        {

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

        }

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

        {

            fa[i]=i;

        }

        sort(a,a+n,cmp);

    /*    for(int i=0;i<n;i++)

        {

            printf("x:%d y:%d\n",a[i].x,a[i].y);

        }*/

        int sum=;

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

        {

            int r=get(a[i].y);

        //    printf("r:%d\n",r);

            if(r!=)

            {

                sum+=a[i].x;

                merge(r,r-);

            }

        }

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

    }

}

巴特西

supermarket

最新文章

热门文章