题意:有一个商店有许多批货,每一批货又有N(0<=N<=(10^4) )个商品,同时每一样商品都有收益(P_i) ,和过期时间(D_i) (1<=(Pi,Di) <=(10^4) ),一旦超过了过期时间,商品就不能再卖。你要做的就是求出每批货最多能得到多少收益。
方法一分析:贪心:对于每个天数t,在保证不卖出过期商品的前提下,尽量卖出收益前t大的商品。把商品按照过期时间从小到大排序,建立一个小根堆,扫描所有商品。如果过期时间等于堆的size,则与堆顶(堆中最小权值)比较,如果大于则把哪个商品挤出堆.如果过期时间大于堆的size,直接入堆即可.最后堆中商品即卖出的商品.
//#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
using namespace std;
inline int read(){
int x=0,o=1;char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
if(ch=='-')o=-1,ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x*o;
}
const int N=10005;
struct node{
int val,t;
bool operator < (const node x) const{
return val>x.val;
}
}a[N];
inline bool cmp(const node &x,const node &y){return x.t<y.t;}
priority_queue<node>q;
int main(){
int n,ans;
while(scanf("%d",&n)!=EOF){
if(!n){puts("0");continue;}
for(int i=1;i<=n;++i){
a[i].val=read();
a[i].t=read();
}
sort(a+1,a+n+1,cmp);
node temp;temp.val=a[1].val;temp.t=a[1].t;q.push(temp);
for(int i=2;i<=n;++i){
int sum=q.size();
if(a[i].t==sum){
if(a[i].val>q.top().val){
q.pop();
temp.val=a[i].val;temp.t=a[i].t;q.push(temp);
}
}
if(a[i].t>sum){temp.val=a[i].val;temp.t=a[i].t;q.push(temp);}
}
ans=0;
while(!q.empty()){ans+=q.top().val;q.pop();}
printf("%d
",ans);
}
return 0;
}
方法二:不用堆而用并查集来做。按照收益从大到小排序。
#include<bits/stdc++.h>
using namespace std;
const int N=10005;
int n,ans;
int f[N];
struct node{int t,val;}a[N];
bool cmp(const node &x,const node &y){return x.val>y.val;}
int find(int x){
if(f[x]<0) return x;
return f[x]=find(f[x]);
}
int main(){
while(cin>>n){
ans=0;
memset(f,-1,sizeof(f));
for(int i=1;i<=n;i++)
scanf("%d%d",&a[i].val,&a[i].t);
sort(a+1,a+1+n,cmp);
for(int i=1;i<=n;i++){
int r1=find(a[i].t);
if(r1>0) ans+=a[i].val,f[r1]=r1-1;
}
printf("%d
",ans);
}
return 0;
}