[CF3B] Lorry - 贪心

有一辆载重量为 v 的货车，准备运送两种物品。物品 A 的重量为 1，物体 B 的重量为 2，每个物品都有一个价值。求货车可以运送的物品的最大价值。

Solution

考虑把物品分为两类，枚举 B 类选多少个，考虑到每一类中一定会优先选择价值最高的那些，排序即可

#include <bits/stdc++.h>

using namespace std;

#define int long long

int n,v,p,q,ans,ans2,ans3,c[200005],d[200005];

vector <pair<int,int> > a,b;

signed main() {

    ios::sync_with_stdio(false);

    cin>>n>>v;

    for(int i=1;i<=n;i++) {

        cin>>p>>q;

        if(p==1) a.push_back(make_pair(q,i));

        if(p==2) b.push_back(make_pair(q,i));

    }

    sort(a.rbegin(),a.rend());

    sort(b.rbegin(),b.rend());

    for(int i=1;i<a.size();i++) a[i].first+=a[i-1].first;

    for(int i=1;i<b.size();i++) b[i].first+=b[i-1].first;

    for(int i=1;i<=a.size();i++) c[i]=a[i-1].first;

    for(int i=a.size()+1;i<=n;i++) c[i]=c[a.size()];

    for(int i=1;i<=b.size();i++) d[i]=b[i-1].first;

    for(int i=0;i<=b.size();i++) {

        int tmp=d[i]+c[v-i*2];

        if(ans<tmp) {

            ans=tmp;

            ans2=i;

            ans3=min((int)(a.size()),min(n*2,v-i*2));

        }

    }

    cout<<ans<<endl;

    for(int i=0;i<ans2;i++) cout<<b[i].second<<" ";

    for(int i=0;i<ans3;i++) cout<<a[i].second<<" ";

}

巴特西

[CF3B] Lorry - 贪心

Solution

最新文章

热门文章