Codeforces[1900] 3B Lorry

题目描述

• 给你 n n n个物品，然后给你一个体积为 v v v的背包。
• 每个物品的体积只可能是 1 1 1或 2 2 2。
• 每个物品都有价值。
• 问你这个背包最多装多少价值的物品走。
• 且输出取走的物品集合序列。

数据范围

• 1 ≤ n ≤ 1 0 5 1 \leq n \leq 10^5 1≤n≤105
• 1 ≤ v ≤ 1 0 9 1 \leq v \leq 10^9 1≤v≤109

测试样例

input
3 2
1 2
2 7
1 3

output
7
2

思路

贪心+二分。

我们先对体积为 1 1 1和体积为 2 2 2的物品集合分别排序，然后求出两个物品集合价值的前缀和。

枚举体积为 1 1 1的物品的前缀和，二分出能装下的最大的体积为 2 2 2的物品的价值。

时间复杂度

O ( n l o g n ) O(nlogn) O(nlogn)

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 500010;

int n, v;
pair<int, int> obj1[maxn], obj2[maxn];
long long sum1[maxn], sum2[maxn];

bool cmp(pair<int, int> A, pair<int, int> B) {
	return A.first > B.first;
}

void work() {
	
	scanf("%d%d", &n, &v);
	int sz1 = 0, sz2 = 0;
	
	for (int i = 1; i <= n; ++i) {
		int x, y;
		scanf("%d%d", &x, &y);
		if (x == 1) obj1[++sz1] = make_pair(y, i);
		else obj2[++sz2] = make_pair(y, i);
	}
	
	sort(obj1 + 1, obj1 + sz1 + 1, cmp);
	sort(obj2 + 1, obj2 + sz2 + 1, cmp);
	
	for (int i = 1; i <= sz1; ++i) sum1[i] = sum1[i - 1] + obj1[i].first;
	for (int i = 1; i <= sz2; ++i) sum2[i] = sum2[i - 1] + obj2[i].first;
	
	int x = 0, y = 0, ans = 0;
	for (int i = 0; i <= min(sz1, v); ++i) {
		int l = 0, r = sz2, Ans = 0;
		while (l < r) {
			int mid = l + r + 1 >> 1;
			if (2 * mid <= v - i) Ans = mid, l = mid;
			else r = mid - 1;
		}
		int tmp = sum1[i] + sum2[Ans];
		if (tmp > ans) {
			ans = tmp;
			x = i;
			y = Ans;
		}
	}
	
	printf("%d\n", ans);
	
	for (int i = 1; i <= x; ++i) printf("%d ", obj1[i].second);
	for (int i = 1; i <= y; ++i) printf("%d ", obj2[i].second);
	
}

int32_t main() {
	work();
}