题目大意:n个物品,每个物品有一定的保质期d和一定的利润p,一天只能出售一个物品,问最大利润是多少?
题解:这是一个贪心的题目,有两种做法。
1 首先排序,从大到小排,然后每个物品,按保质期从后往前找,找到第一个没被占用的日期,然后出售。
code:
#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> using namespace std; typedef long long ll; const ll N=1e4+7; struct stu{ ll a,b; bool friend operator < (const stu &x,const stu &y){ if(x.a!=y.a) return x.a>y.a; else return x.b>y.b; } }arr[N]; bool mark[N]; int main(){ ll n; while(cin>>n){ for(ll i=1;i<=n;i++){ scanf("%d%d",&arr[i].a,&arr[i].b); } memset(mark,0,sizeof mark); ll sum=0; sort(arr+1,arr+1+n); for(ll i=1;i<=n;i++){ if(mark[arr[i].b]==0) { sum+=arr[i].a; mark[arr[i].b]=1; } else { for(ll j=arr[i].b;j>=1;j--){ if(!mark[j]){ sum+=arr[i].a; mark[j]=1; break; } } } } cout<<sum<<endl; } return 0; }
2 用并查集来维护一下日期,如果说日期a被占用了,fa[a]=a-1,就是往前提上一天,
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const ll N=1e4+7;
struct stu{
ll a,b;
bool friend operator < (const stu &x,const stu &y){
if(x.a!=y.a) return x.a>y.a;
else return x.b>y.b;
}
}arr[N];
ll fa[N];
ll find(ll x){
if(fa[x]==-1) return x;
else return fa[x]=find(fa[x]);
}
int main(){
ll n;
while(cin>>n){
for(ll i=1;i<=n;i++){
scanf("%lld%lld",&arr[i].a,&arr[i].b);
}
sort(arr+1,arr+1+n);
memset(fa,-1,sizeof fa);
ll sum=0;
for(ll i=1;i<=n;i++){
ll c=find(arr[i].b);
if(c>0){
sum+=arr[i].a;
fa[c]=c-1;
}
}
cout<<sum<<endl;
}
return 0;
}
反思:这是完全是一个贪心的题目,并查集只是一种让他跑的更快的工具而已,可能是专项训练的缘故,思维被束缚了,不敢往贪心方向想....