【POJ】1456 supermarket
給定 n 件物品，第 i件物品有如下資訊：
賣出去可以得到pi的收益，
過期時間為di ，過了過期時間就不能再賣出去，
賣掉一件物品要用 1 的時間，求最大收益，
多組資料，每組資料一行，首先一個整數 n然后 n對數pi ,di ，以檔案終止符結束，
0≤n≤10000
1≤pi,di ≤10000 ，
思路
先按收益排序，
用剩余過期時間做并查集，
若沒有過時，
加收益，剩余過期時間-1；
代碼
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct jgt
{
int d,p;
}a[10010];
int n,f[10010];
int find(int x)//找代表值
{
if(x==f[x]) return x;
return f[x]=find(f[x]);
}
bool cmp(jgt t1,jgt t2)
{
return t1.p>t2.p;
}
int main()
{
int mx,ans,i,t;
while(cin>>n)
{
for(mx=0,i=0;i<n;mx=max(mx,a[i].d),i++)
scanf("%d%d",&a[i].p,&a[i].d);
for(i=0;i<=mx;f[i]=i,i++);
sort(a,a+n,cmp);//先按收益排序
for(ans=0,i=0;i<n;i++)
{
t=find(a[i].d);
if(t>0)
{
ans+=a[i].p;//加收益
f[t]=t-1;//剩余過期時間-1
}
}
printf("%d\n",ans);
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/252053.html
標籤：其他
上一篇：C語言實作通訊錄系統
下一篇：C++實作Fibonacci數列