【POJ】1456 supermarket 给定 n 件物品，第 i件物品有如下信息：
卖出去可以得到pi的收益。
过期时间为di ，过了过期时间就不能再卖出去。
卖掉一件物品要用 1 的时间，求最大收益。
多组数据，每组数据一行，首先一个整数 n然后 n对数pi ,di ，以文件终止符结束。
0≤n≤10000
1≤pi,di ≤10000 。
思路 【【POJ】1456 supermarket】先按收益排序。
用剩余过期时间做并查集。
若没有过时。
加收益，剩余过期时间-1；
代码
#include
#include
#include
#include
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;
i0)
{ans+=a[i].p;
//加收益
f[t]=t-1;
//剩余过期时间-1
}
}
printf("%d\n",ans);
}
return 0;
}
推荐阅读
- 问题 K: 最勇敢的机器人(并查集＋背包)
- POJ - 2236Wireless Network （并查集）
- *HDU - 2473Junk-Mail Filter （并查集--删点操作）
- HDU - 1863 畅通工程（并查集+最小生成树）
- 《C语言每日一练》|《画解数据结构》（3 - 4）- 最小生成树