自动搬运

查看原文

来自洛谷，原作者为

	ElectricArc お持ちなさい　あなたの望んだその星を

搬运于2025-08-24 23:17:38，当前版本为作者最后更新于2025-06-26 18:57:21，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意

变量 $A$、$B$、$C$、$D$ 的初始值分别为 $A_0$、$B_0$、$C_0$、$D_0$。

有 $N$ 张卡牌，每张卡牌会使变量 $T_i$ 的值增加 $U_i$。每张卡牌最多只能使用一次，用完即消失。

选用恰好 $K$ 张卡牌最大化 $A\cdot B\cdot C\cdot D$ 的值。

思路

我们考虑贪心，每次都拿一张目前能使总体积增大最多的卡牌，一直贪下去即可。

现在考虑如何找到目前最优的卡牌。

• 同个变量（字母）的卡牌按大小降序排序。
• 取每个变量中卡牌最大的那一张，设为 $d_i \ (i \in \{A,B,C,D\})$，分别计算使用后增大的体积，取贡献最大的那一张卡牌用掉。

设目前变量的值为 $s_i$，总体积 $S = s_A s_B s_C s_D$。

例如，比较变量 $A$ 或 $B$ 后增大的体积，即比较 $d_A s_B s_C s_D$ 和 $s_A d_B s_C s_D$ 的大小。

但是，我们在算增大的体积时，这些值相乘后直接爆 long long 了。不过很容易发现两边可以同时除以 $s_C s_D$，只需要比较 $d_A s_B$ 和 $s_A d_B$ 的大小即可，这也是其他题解的做法之一。

考虑比较增加变量 $i$ 或 $j$ 后增大的体积，即比较 $\dfrac{d_i S}{s_i}$ 和 $\dfrac{d_j S}{s_j}$ 的大小，发现可以约掉 $S$（而不是两个 $s$），即比较 $\dfrac{d_i}{s_i}$ 和 $\dfrac{d_j}{s_j}$ 的大小。现在只需要分别计算 $\dfrac{d_i}{s_i}$（用 long double 存的话，精度还是够的），求最大值即可。

代码

#include <cstdio>
#include <queue>
using namespace std;

typedef long long ll;

priority_queue<int> q[4];
ll s[4];

int main() {
	int n, k;
	scanf("%d %d", &n, &k);
	for (int i = 0; i < 4; i++) scanf("%lld", &s[i]);
	for (int i = 1; i <= n; i++) {
		char t;
		int u;
		scanf(" %c %d", &t, &u);
		q[t - 'A'].push(u);
	}
	for (int i = 0; i < 4; i++) q[i].push(0); // 防止队首取空
	for (int i = 1; i <= k; i++) {
		int pre[4];
		for (int j = 0; j < 4; j++) pre[j] = q[j].top();
		int pos = -1;
		long double mx = 0;
		for (int j = 0; j < 4; j++) {
            long double tmp = pre[j] / (long double)s[j];
			if (mx < tmp) mx = tmp, pos = j;
		}
		s[pos] += pre[pos];
		q[pos].pop();
		printf("%c %d\n", pos + 'A', pre[pos]);
	}
	
	return 0;
}