nfls15095 Atcoder-abc123_d 蛋糕

Atcoder-abc123_d
AT 小卖部从下学期开始售卖带有数字形状的蛋糕，\(X\)，\(Y\) 和 \(Z\) 种蛋糕分别带有 \(1\) 形，\(2\) 形和 \(3\) 形蜡烛，而且每个蛋糕都有美味值，如下所示：

• 带有 \(1\) 形蜡烛的美味值有： \(A_1,A_2,\cdots,A_X\)
• 带有 \(2\) 形蜡烛的美味值有： \(B_1,B_2,\cdots,B_Y\)
• 带有 \(3\) 形蜡烛的美味值有： \(C_1,C_2,\cdots,C_Z\)

你决定购买三个蜡烛不同的蛋糕，请你将每种方案的美味值由大到小排序，依次打印前 \(K\) 种方案的美味值。
一行四个整数\(X,Y,Z,K\)如题

一行\(X\)个整数，表示第一种蛋糕的美味值

一行\(Y\)个整数，表示第二种蛋糕的美味值

一行\(Z\)个整数，表示第三种蛋糕的美味值
\(K\)行，从大到小输出前\(K\)种方案的美味值

方法一：
枚举，前面两个序列合并求和o(1e6),sort求前k大，再和第三个合并求和，o(1e6),sort求前k大，
方法二：
堆。将三个数组升序排序，先把最小的三元组（1，1，1），放入堆中，我们每次从堆中取出最小的三元组，即为当前轮的答案，再将它的每一维分别进行调整，向堆中加入三个三元组，即可保证每次取出的都是最小的。
每轮都会从堆中删除一个，加入三个，一共k轮，故堆中的元素不会超过2k，空间得到保证。用set更好，避免完全相同的下标三元组。
另：set存放不同的值，要强行钦定一个顺序。下标不同但值相同的元素组，都会保留。

    if (p.i != q.i) {
        return p.i > q.i;
    } else if (p.j != q.j) {
        return p.j > q.j;
    } else {
        return p.k > q.k;
    }

完整代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
struct chs {
int i, j, k;
chs(int x = 0, int y = 0, int z = 0) {
    i = x; j = y; k = z;
}
};
ll a[1005];
ll b[1005];
ll c[1005];
bool operator <(chs p, chs q) {
    if (a[p.i] + b[p.j] + c[p.k] != a[q.i] + b[q.j] + c[q.k]) {
        return a[p.i] + b[p.j] + c[p.k] > a[q.i] + b[q.j] + c[q.k];
    }
    if (p.i != q.i) {
        return p.i > q.i;
    } else if (p.j != q.j) {
        return p.j > q.j;
    } else {
        return p.k > q.k;
    }
}
set<chs> st;
int main() {
    int X, Y, Z, K;
    scanf("%d %d %d %d", &X, &Y, &Z, &K);
    for (int i = 0; i < X; i++) {
        scanf("%lld", &a[i]);
    }
    for (int i = 0; i < Y; i++) {
        scanf("%lld", &b[i]);
    }
    for (int i = 0; i < Z; i++) {
        scanf("%lld", &c[i]);
    }
    sort(a, a + X, greater<ll>());
    sort(b, b + Y, greater<ll>());
    sort(c, c + Z, greater<ll>());
    st.insert(chs(0, 0, 0));
    while (K--) {
        chs x = *st.begin();
        st.erase(st.begin());
        printf("%lld\n", a[x.i] + b[x.j] + c[x.k]);
        if (x.i < X - 1) st.insert(chs(x.i + 1, x.j, x.k));
        if (x.j < Y - 1) st.insert(chs(x.i, x.j + 1, x.k));
        if (x.k < Z - 1) st.insert(chs(x.i, x.j, x.k + 1));
    }
    return 0;
}