题意:
一辆车可以承载体积V的货物,A种物品1个单位体积,B种2个单位体积,某种物品虽然体积相同但是贡献不同
给出N个物品它的物品类型(1,2)和贡献值。求这辆车最大可以拿到多大的贡献。
题解:贪心题啊。
明显地,对于体积相同的,我们肯定要选贡献最大的。那我们就从大到小选。我们先从大到小分别求这两种物品的前缀和。一起考虑两种物品,如果组成体积相同时,就选最大贡献的,如果贡献相同,就选体积最小的。
AC代码:
#include<bits/stdc++.h>
using namespace std;
int t1,t2;
int s1[100010],s2[100010];
pair<int,int>c1[100010],c2[100010];
bool cmp(pair<int,int>a,pair<int,int>b)
{
return a.first > b. first;
}
int main()
{
// freopen("in.txt","r",stdin);
int n,v;
cin>>n>>v;
for(int i=0;i<n;i++)
{
int t,p;
cin>>t>>p;
if(t==1){
c1[t1++] = make_pair(p,i+1);
}
else
c2[t2++] =make_pair(p,i+1);
}
sort(c1,c1+t1,cmp);
sort(c2,c2+t2,cmp);
s1[0] = s2[0] = 0;
for(int i=0;i<t1;i++){
s1[i+1]=s1[i]+c1[i].first;
}
for(int i=0;i<t2;i++){
s2[i+1]=s2[i]+c2[i].first;
}
int ans = -1;
int tmp = -1;
for(int i=0;i<=t2;i++)
{
if(i * 2 <= v && s1[ min(v-i*2, t1) ] + s2[i] > ans){
ans = s1[ min(v-i*2,t1) ] + s2[i] ;
tmp = i;
}
}
cout<<ans<<endl;
for(int i=0;i<min(v-tmp*2,t1);i++) cout<<c1[i].second<<endl;
for(int i=0;i<tmp;i++) cout<<c2[i].second<<endl;
return 0;
}