正经题解｜挖矿

题目大意

给出$n$件商品的数量与价值，以及背包的体积$w$，求怎样的装载策略可以在不超过背包体积的情况下让拿取物品到达价值最大化。

题意分析

求价值最大化的物品搭配策略，要求数量总额不超过背包体积。

解题思路

根据题目给出的数据范围，每个物品的最大价值$v_i \leq 10^9$，因此此题用背包去求解是固然求不了的。

我们不妨转换下题意，将每种商品视为$s_i / 64$个价值总额为$v_i \times 64$的商品(不足64个的部分分离出来作为一个商品)，那么此题就可以由背包问题转型为贪心类型的问题。

那么当我们从价值最大往最小的去取时，此时的方案一定是最优的。先从最大到最小去取，当取完完整的个体后，再去考虑剩下不够64个的商品。最后判断取与不取哪种方法最优。

在取值的过程当中，我们可以利用优先队列进行维护不足64个的商品，在进行判断时直接取队首即可。

实现的方法很多，只需要将时间复杂度压缩至$O(nlogn)$即可。

时间复杂度解析

利用优先队列进行维护，时间复杂度为$O(nlogn)$

代码演示

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 55, INF = 1e9, MOD = 1e9 + 7;
int n, w;
long long ans;
struct st {
	int s, v;
	/*
	重载运算符，在排序结构体时以矿物价值为关键字降序排列。 
	*/
	bool operator < (const st &x) const { 
		return x.v < v;
	}
} a[N]; 
priority_queue<long long> q;
signed main() {
	scanf("%d%d", &n, &w);
	for (int i = 1; i <= n; i++) scanf("%d", &a[i].s);
	for (int i = 1; i <= n; i++) scanf("%d", &a[i].v);
	sort(a + 1, a + 1 + n);
	for (int i = 1; i <= n; i++) {
		/*
		如果取堆顶比取当前满格的更优，就取堆中的，直到不优或取完。 
		*/ 
		while (q.size() && w && q.top() >= 64ll * a[i].v) {
			w--;
			ans += q.top();
			q.pop();
		}
		/*
		取满格。 
		*/
		if (64ll * w <= a[i].s) {
			/*
			如果取完这次背包就会满，累加完答案后直接退出。 
			*/
			ans += 64ll * w * a[i].v;//因为背包空间不足，取后会满，所以这里统计个数的标准是背包空间。 
			w = 0;
			break;
		}
		/*
		将剩余不足满格的矿物放入堆中，需要直接将总价值计算出来，所有堆中的物品占用空间都是1。
		如果正好拿满，但也会将一个空的价值放入堆中，但此时不会导致错误，
		因为取空的是一种非常劣的决策，根据我们的贪心策略是会避免掉这个的。 
		*/
		int k = a[i].s / 64 * 64;//k代表这轮我取了多少个当前矿物。 
		ans += 1ll * k * a[i].v;//因为矿物不够拿，取后背包不会满，所以这里统计个数的标准是满格矿物数量。		 
		a[i].s -= k;
		w -= k / 64;
		q.push(1ll * a[i].s * a[i].v);
	}
	/*
	拿堆中剩余的直到拿完或背包已满。 
	*/ 
	while (q.size() && w) {
		ans += q.top();
		w--;
		q.pop();
	}
	printf("%lld\n", ans);
	return 0;
}