【POJ1456】Supermarket（贪心）---饶文津

题意

每个商品有过期日期和价格，每天可以卖一个商品，必须在过期前出售才能收益，求最大收益。

题解

贪心，按价格排序，再将它放在过期日期当天出售，若当天已经用了，就往前找可用的日子，若找到了还要标记这一天已用。

代码#include <cstdio> #include <cstring> #include <algorithm> #include <iostream> using namespace std; struct pro{ int p,d; }p[10005]; int cmp (pro a,pro b){ return a.p>b.p||a.p==b.p&&a.d>b.d; } int v[10005]; int main() { int n; while(~scanf("%d",&n)){ int ans=0; for(int i=1;i<=n;i++) scanf("%d%d",&p[i].p,&p[i].d); sort(p+1,p+1+n,cmp); memset(v,0,sizeof v); for(int i=1,j;i<=n;i++){ for(j=p[i].d;v[j]&&j;j--); if(j){v[j]=1; ans+=p[i].p;} } printf("%dn",ans); } return 0; } ---来自腾讯云社区的---饶文津