codeforce 3B lorry (贪心)

有货车运量V；

有若干物品A 占2单位体积，有若干物品B占1单位体积；

相同种类的物品价值不一定一样；

序号按照输入顺序而定；

问货车可以拉走最多多少价值的物品，并输出所选物品的序号；

思路：贪心，先把A填到不能填，然后再补B，补完B后再考虑用B去替换前面A，此策略必定最优；考虑到B物品的可补行！

因为涉及变量较多，时刻注意A，B，空余V的数量关系；

下面是AC代码

#include <iostream>
#include <algorithm>
#define STD std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
const int maxn=1e5+10;
typedef long long ll;
struct point{
	int id;
	ll v;
}a[maxn],b[maxn];
int sto[maxn];
bool cmp(point a,point b)
{
	return a.v>b.v;
}
int main() 
{
	STD;
	int n,v,k,q,id,p;
	int vv;
	cin>>n>>v;
	k=q=1;p=0;
	for (int i=0;i<n;i++)
	{	
		cin>>id>>vv;
		id==1?(a[k].v=(ll)vv,a[k++].id=i+1):(b[q].v=(ll)vv,b[q++].id=i+1);
	} 
	sort(a+1,a+1+k,cmp);
	sort(b+1,b+1+q,cmp);
	int a_head=1;
	int b_last=min(v/2,q-1);
	int re=(v%2==1)?(v-min(v-1,2*(q-1))):(v-min(v,2*(q-1)));
	ll sum=0;
	k-=1;
	for (int i=1;i<=b_last;i++)
		sum+=b[i].v;
	while (re>0&&k>0)
	{
		sum+=a[a_head++].v;
		sto[p++]=a[a_head-1].id;
		k--;
		re--;
	}
	while (k>=2&&b_last>=1)
	{
		if (a[a_head].v+a[a_head+1].v>b[b_last].v)
		{
			sum-=b[b_last].v;
			sum+=(a[a_head].v+a[a_head+1].v);
			sto[p++]=a[a_head].id;
			sto[p++]=a[a_head+1].id;
		}
		else
			break;
		k-=2;
		b_last--;
		a_head+=2;
	}
	if (k==1&&a[a_head].v>b[b_last].v&&b_last>=1)
	{
		sum+=a[a_head].v-b[b_last].v;
		b_last--;
		sto[p++]=a[a_head].id;
	}
	cout<<sum<<endl;
	for (int i=b_last;i>=1;i--)
		sto[p++]=b[i].id;
	for (int i=0;i<p;i++)
		cout<<sto[i]<<" ";
	cout<<endl;
	return 0;
}