题解 CF3B 【Lorry】
皎月半洒花
2019-02-14 18:37:07
说实话我感觉写完这道题之后，打算来题解区看看有没有什么更好的Idea，然后看完题解之后我自己都不会做了……
其实是一个非常简单的贪心思路，就是如果两件重量为1的商品合成一件的话，比重量为2的要优我们就选合起来的。
$Somebody$谈过一个小Idea，就是看上去我们期望每次取偶数个。那么我们一开始如果$M$是奇数，就从重量为1的那一堆选一个最大的……（虽然我不知道这个到底有没有用但是听起来挺科学）
有些小细节需要注意。其中拿出来一个说一下：边界问题其实不需要考虑得太仔细，只要我们一开始memset整个数组为-INF，那么当一种重量的用完了，另一种重量的没用完时，取max之后不会出现越界的情况
```cpp
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#define MAXN 200020
#define pb push_back
#define rep(i, a, x) for(i = a ; i <= x ; ++ i)
using namespace std ;
struct Data{
int num ,val ;
} base1[MAXN], base2[MAXN] ; int N, M, p, v, v1, v2, c ;
long long Ans ; int tot1, tot2, t1, t2, i ; vector <int> ans ;
inline bool Comp(Data a, Data b){ return a.val > b.val ; }
int main(){
cin >> N >> M ;
memset(base1, -63, sizeof(base1)) ;
memset(base2, -63, sizeof(base2)) ;
for (i = 1 ; i <= N ; ++ i){
scanf("%d%d", &p, &v) ;
if (p > 1) base2[++ tot2].val = v, base2[tot2].num = i ;
else/*qwq*/base1[++ tot1].val = v, base1[tot1].num = i ;
}
sort(base1 + 1, base1 + tot1 + 1, Comp),
sort(base2 + 1, base2 + tot2 + 1, Comp) ;
// for (i = 1 ; i <= N ; ++ i) cout << base1[i].num << " " << base1[i].val << " qwwq " ;
// for (i = 1 ; i <= N ; ++ i) cout << base2[i].num << " " << base2[i].val << " qwwq " ;
if (M & 1) ans.pb(base1[1].num), Ans += base1[1].val, ++ t1, M -- ;
while (M > 1){//此处>1是选v=2时防止越界
v2 = base2[t2 + 1].val ;
if (t1 >= tot1 && t2 >= tot2) break ;
v1 = base1[t1 + 1].val + base1[t1 + 2].val ;
if (t1 + 2 > tot1) v1 = base1[t1 + 1].val, c = 1 ; else c = 2 ;
if (v1 >= v2){
Ans += v1 ; M -= c ;
rep(i, 1, c) ans.pb(base1[++ t1].num) ;
}
else Ans += v2, M -= 2, ans.pb(base2[++ t2].num) ;
}//因为while的条件是M>1,所以需要判断一下是不是还可以选。
if (M && t1 < tot1) Ans += base1[++ t1].val, ans.pb(base1[t1].num) ; if (Ans < 0) return puts("0\n"), 0 ;
cout << Ans << endl ; for (vector<int> :: iterator k = ans.begin() ; k != ans.end() ; ++ k) cout << *k << " " ;
}
```