题解：P12712 [KOI 2021 Round 1] 超矩形

· · 题解

题意

变量 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 的值。

思路

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

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

设目前变量的值为 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;
}