题解 CF3B 【Lorry】
Heartlessly
2019-06-24 07:43:50
## Description
有一个体积为 $v$ 的背包，一共有 $n$ 个物品，每个物品的体积为 $t_i$，价值为 $p_i$ 。现要从中取若干物品放入背包，使背包中物品的价值和最大。
$(1 \leq n \leq 10^5,1 \leq v \leq 10^9,1 \leq t_i \leq 2,1 \leq p_i \leq 10^4)$
## Solution
发现物品的体积只有 $2$ 种，分别是 $1$ 和 $2$ 。我们可以根据体积把它们分成两类。
假如所有物品都是同一类的，一个很显然的贪心是选价值较大的更优，所以对于每一类我们将物品按价值从大到小排序。
考虑枚举体积为 $1$ 的物品放多少个，剩下的空间全部放体积为 $2$ 的物品，判断是否能够更新答案即可。时间复杂度为排序的复杂度 $O(n \log n)$ 。
## Code
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
template <class T>
inline void read(T &x) {
x = 0;
char c = getchar();
bool f = 0;
for (; !isdigit(c); c = getchar()) f ^= c == '-';
for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
x = f ? -x : x;
}
template <class T>
inline void write(T x) {
if (x < 0) {
putchar('-');
x = -x;
}
T y = 1;
int len = 1;
for (; y <= x / 10; y *= 10) ++len;
for (; len; --len, x %= y, y /= 10) putchar(x / y + 48);
}
const int MAXN = 1e5;
int n, v, cnt1, cnt2, pos1, pos2, ans, sum, pre[MAXN + 5];
struct Node {
int p, id;
inline friend bool operator<(Node x, Node y) {
return x.p > y.p;//按价值从大到小排序
}
} t1[MAXN + 5], t2[MAXN + 5];
int main() {
read(n), read(v);
for (int t, p, i = 1; i <= n; ++i) {
read(t), read(p);
if (t == 1) {
t1[++cnt1].p = p;
t1[cnt1].id = i;
} else {
t2[++cnt2].p = p;
t2[cnt2].id = i;
}//根据体积分成两类
}
sort(t1 + 1, t1 + cnt1 + 1), sort(t2 + 1, t2 + cnt2 + 1);
for (int i = 1; i <= cnt2; ++i) pre[i] = pre[i - 1] + t2[i].p;
//预处理出体积为 2 的物品价值的前缀和
for (int i = 0; i <= min(v, cnt1); ++i) {//选了 i 个体积为 1 的物品
sum += t1[i].p;//体积为 1 的物品价值和
//体积为 2 的物品选了 min(cnt2, (v - i) / 2) 个
if (sum + pre[min(cnt2, (v - i) / 2)] > ans) {//如果更优
ans = sum + pre[min(cnt2, (v - i) / 2)];
pos1 = i, pos2 = min(cnt2, (v - i) / 2);//记录该方案的位置
}
}
write(ans);
putchar('\n');
for (int i = 1; i <= pos1; ++i) {
write(t1[i].id);
putchar(' ');
}
for (int i = 1; i <= pos2; ++i) {
write(t2[i].id);
putchar(' ');
}
putchar('\n');
return 0;
}
```