Codeforces 3B. Lorry

Codeforces 3B. Lorry

Codeforces 3B. Lorry
传送门：

题目大意：
首先，题目将为你提供两个数字n和v，在接下来的n行中，每一行都会提供两个数ai、bi（ai=2或1，bi>0），我们需要从中选出一些序号i使得在∑ai<=v的情况下，令∑bi取得的值最大。

主要思路：
首先，因为有两种不同的ai取值，我们不妨由此分类，计为类1和类2，并对它们分别排序。我们知道，如果想要取得最大值的话，一定是要尽量地使用掉v，如果v是奇数的话，类2只有偶数，所以我们肯定需要放一个类1的数，我们贪心一点，就放最大的那个。于是，接下来的过程中只要我们每次放两个类1或一个类2就可以，到至于放哪一种，肯定是先大的那种。

	代码如下：

#include <bits/stdc++.h>using namespace std;bool cmp(pair<int,int> a,pair<int,int> b)
{return (a.first>b.first);
}
int main()
{int n,v,x=0,j=0,k=0,l,m;cin>>n>>v;vector<pair<int,int> >a,b;for(int i=0;i<n;i++){int c,d;cin>>c>>d;if(2-c)a.push_back({d,i+1});else b.push_back({d,i+1});}sort(a.begin(),a.end(),cmp);sort(b.begin(),b.end(),cmp);vector<int> c;l=a.size();m=b.size();a.push_back({0,0});b.push_back({0,0});if(1==v%2){if(a.size()==1&&v==1){cout <<0<<endl;return 0;}x+=a[j].first;c.push_back(a[j++].second);v--;}while(v>1&&m-k!=0){if(l-j<2||b[k].first>a[j].first+a[j+1].first){x+=b[k].first;c.push_back(b[k++].second);}else{x+=a[j].first+a[j+1].first;c.push_back(a[j++].second);c.push_back(a[j++].second);}v-=2;}while(v>0&&l-j>0){x+=a[j].first;c.push_back(a[j++].second);v--;}cout<<x<<endl;for(int i=0;i<c.size();++i)cout<<c[i]<<' ';return 0;
}