超市里有n件商品,每件商品都有利润v[i] 和过期时间tm[i] ,
每天只能卖一件商品,过期商品不能卖。
求可以得到的最大收益
#include "bits/stdc++.h" using namespace std; const int N=1e5+5; struct T{ int v,tm; }a[N]; int n; bool cmp(T &A,T &B){ if(A.tm==B.tm) return A.v>B.v; return A.tm<B.tm; } void sov(){ int i,t; priority_queue<int,vector<int>,greater<int> > q; for(i=1;i<=n;i++) cin>>a[i].v>>a[i].tm; sort(a+1,a+1+n,cmp); t=0; int cnt=0; for(i=1;i<=n;i++){ if(a[i].tm>cnt) cnt++,t+=a[i].v,q.push(a[i].v); else if(a[i].v>q.top()) t-=q.top(),t+=a[i].v,q.pop(),q.push(a[i].v); } cout<<t<<endl; } main(){ while(cin>>n) sov(); }
标签:cnt,145,int,top,超市,tm,acw From: https://www.cnblogs.com/towboa/p/16945292.html