贪心】"/>
Supermarket【并查集】【贪心】
>Description
有一个商店有许多批货,每一批货又有N(0<=N<=10^4104 )个商品,同时每一样商品都有收益PiP_iPi ,和过期时间DiD_iDi (1<=Pi,DiPi,DiPi,Di <=10^4104 ),一旦超过了过期时间,商品就不能再卖。
你要做的就是求出每批货最多能得到多少收益。
>Input
多组数据,每组先给出一个整数N,表示这批货的商品个数。
然后有N对数,每对数有两个用空格隔开的正整数Pi,DiP_i,D_iPi,Di ,表示第i个商品的收益和过期时间。相邻两对数之间用空格隔开。
输入以一个文件终止符结束,并且保证所有输入数据正确。
>Output
对于每组数据,输出一行一个整数表示该批货物能卖出的最大价格。
>Sample Input
4 50 2 10 1 20 2 30 1
7 20 1 2 1 10 3 100 2 8 2 5 20 50 10
>Sample Output
80
185
>解题思路
并查集+贪心。
按照价值从大到小排序,也就是先卖价格最大的;看看当前商品能最晚卖出的时间,那时候是不是已经有商品卖,如果没有,就直接在那个时间卖掉,如果有,就把时间往前推。
>代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct ooo
{int c,t;
}a[100005];
int n,cc[100005],ans,tt;
bool lil(ooo aa,ooo bb)
{if(aa.c!=bb.c) return aa.c>bb.c;else return aa.t>bb.t;
}
int find(int v)
{if(cc[v]==v) return v;return cc[v]=find(cc[v]);
}
void work()
{ans=0;for(int i=1;i<=100000;i++)cc[i]=i;for(int i=1;i<=n;i++)scanf("%d%d",&a[i].c,&a[i].t);sort(a+1,a+1+n,lil);for(int i=1;i<=n;i++){tt=find(a[i].t);if(tt!=0) //如果有时间可以卖出{cc[tt]=tt-1;ans+=a[i].c; //直接加上价值}}printf("%d\n",ans);
}
int main()
{while(scanf("%d",&n)==1) work();return 0;
}
更多推荐
Supermarket【并查集】【贪心】
发布评论