学步园

分开处理，把1和2分开存放到不同的容器中，然后分别排序。

先处理1，再处理2，再处理跨1和2的。

#include <cstdio>
#include <vector>
#include <cmath>
#include <iterator>
#include <algorithm>
using namespace std;

class node{
public:
	int c;
	int idx;
	node(int ac=0,int ai=0): c(ac),idx(ai) {}
	bool operator<(const node& a) const {return c>a.c;}
};

vector<node> one,two;
vector<int> ao,at,aot;
int on,tw,ot;

int main()
{
	int n,v;
	int t,c;
	scanf("%d%d",&n,&v);
	for(int i=0;i<n;i++)
	{
		scanf("%d%d",&t,&c);
		if(t==1) one.push_back(node(c,i+1));
		else two.push_back(node(c,i+1));
	}
	sort(one.begin(),one.end());
	sort(two.begin(),two.end());
	//for one
	on=0;tw=0;ot=0;
	int curc=0,curt=0;
	for( vector<node>::iterator itec=one.begin();itec!=one.end();itec++ )
	{
		if(curt+1<=v)
		{
			curt++;
			on+=itec->c;
			ao.push_back(itec->idx);
		}
	}
	//for two
	curt=0;
	for( vector<node>::iterator itec=two.begin();itec!=two.end();itec++ )
	{
		if(curt+2<=v)
		{
			curt+=2;
			tw+=itec->c;
			at.push_back(itec->idx);
		}
	}
	//for one and tow;
	int pto=0,ptt=0;
	curt=0;
	while(!one.empty()&&!two.empty()&&(pto<one.size()||ptt<two.size()))
	{
		if( curt+1<=v&& ((pto+1<one.size() && one[pto].c+one[pto+1].c>two[ptt].c)||(pto+1==one.size()&&one[pto].c>two[ptt].c)) )
		{
			curt++;
			ot+=one[pto].c;
			aot.push_back(one[pto].idx);
			pto++;
		}
		else if( curt+2<=v&&ptt<two.size() )
		{
			curt+=2;
			ot+=two[ptt].c;
			aot.push_back(two[ptt].idx);
			ptt++;
		}
		else if( curt+1==v&&pto<one.size() ) //如果剩下1个空位，那就放呗。能多放一个是一个。
		{
			curt++;
			ot+=one[pto].c;
			aot.push_back(one[pto].idx);
			pto++;
		}
		else
		{
			pto++;
			ptt++;
		}
	}
	int maxn=max(on,max(ot,tw));
	printf("%d\n",maxn);
	vector<int> ans;
	if(maxn==on) ans=ao;
	else if(maxn==tw) ans=at;
	else if(maxn==ot) ans=aot;
	for(int i=0;i<ans.size();i++)
	{
		printf(i==ans.size()-1?"%d\n":"%d ",ans[i]);
	}
	return 0;
}