Supermarket POJ - 1456（贪心）

题目大意：n个物品，每个物品有一定的保质期d和一定的利润p，一天只能出售一个物品，问最大利润是多少？

题解：这是一个贪心的题目，有两种做法。

1 首先排序，从大到小排，然后每个物品，按保质期从后往前找，找到第一个没被占用的日期，然后出售。

code:

#include<cstdio>

#include<iostream>

#include<cstring>

#include<algorithm>

using namespace std;

typedef long long ll;

const ll N=1e4+;

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=;i<=n;i++){

            scanf("%d%d",&arr[i].a,&arr[i].b);

        }

        memset(mark,,sizeof mark);

        ll sum=;

        sort(arr+,arr++n);

        for(ll i=;i<=n;i++){

            if(mark[arr[i].b]==) {

                sum+=arr[i].a;

                mark[arr[i].b]=;

            }

            else {

                for(ll j=arr[i].b;j>=;j--){

                    if(!mark[j]){

                        sum+=arr[i].a;

                        mark[j]=;

                        break;

                    }

                }

            }

        }

        cout<<sum<<endl;

    }

    return ;

}

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+;

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]==-) return x;

    else return fa[x]=find(fa[x]);

}

int main(){

    ll n;

    while(cin>>n){

        for(ll i=;i<=n;i++){

            scanf("%lld%lld",&arr[i].a,&arr[i].b);

        }

        sort(arr+,arr++n);

        memset(fa,-,sizeof fa);

        ll sum=;

        for(ll i=;i<=n;i++){

            ll c=find(arr[i].b);

            if(c>){

                sum+=arr[i].a;

                fa[c]=c-;

            }

        }

        cout<<sum<<endl;

    }

    return ;

}

反思：这是完全是一个贪心的题目，并查集只是一种让他跑的更快的工具而已，可能是专项训练的缘故，思维被束缚了，不敢往贪心方向想....

巴特西

Supermarket POJ - 1456（贪心）

最新文章

热门文章