题解 | #奥赛组队#

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
const int N = 3005;
struct node {
    int id, num;
    node(int x = 0, int y = 0) : id(x), num(y) {}
    bool operator<(const node &p) const { return num > p.num; }
    bool operator>(const node &p) const { return num < p.num; }
} a[N], b[N];
bool cmpId(const node &x, const node &y) { return x.id < y.id; }
priority_queue<node, vector<node>, greater<node>> q1, q2, q3;
int op[N];
int main() {
    int n, X, Y;
    cin >> n >> X >> Y;
    for (int i = 1; i <= n; i++) { cin >> a[i].num; a[i].id = i; }
    for (int i = 1; i <= n; i++) { cin >> b[i].num; b[i].id = i; }
    // 按编程能力降序选前 X 名加入编程队
    sort(a + 1, a + n + 1);
    long long ans = 0;
    for (int i = 1; i <= X; i++) {
        op[a[i].id] = 1;
        ans += a[i].num;
    }
    // 恢复原顺序
    sort(a + 1, a + n + 1, cmpId);
    // 初始化优先队列
    for (int i = 1; i <= n; i++) {
        q1.push(node(i, a[i].num));        // 编程能力队列
        q2.push(node(i, b[i].num));        // 体育能力队列
        if (op[i] == 1) {
            q3.push(node(i, b[i].num - a[i].num)); // 边际收益队列
        }
    }
    // 选 Y 名体育队成员
    for (int cnt = 0; cnt < Y; cnt++) {
        long long best = LLONG_MIN;
        int id1 = -1, id2 = -1, opt = 0;
        // 方案1：直接选取最高体育能力
        while (!q2.empty() && op[q2.top().id] != 0) q2.pop();
        if (!q2.empty()) {
            best = q2.top().num;
            id1 = q2.top().id;
            opt = 1;
        }
        // 方案2：交换编程队与未选中队员
        while (!q3.empty() && op[q3.top().id] != 1) q3.pop();
        while (!q1.empty() && op[q1.top().id] != 0) q1.pop();
        if (!q3.empty() && !q1.empty()) {
            long long gain = q3.top().num + q1.top().num;
            if (gain > best) {
                best = gain;
                id1 = q3.top().id;
                id2 = q1.top().id;
                opt = 2;
            }
        }
        ans += best;
        if (opt == 1) {
            op[id1] = 2;
        } else {
            op[id1] = 2;
            op[id2] = 1;
            q1.pop();
            q3.pop();
            q3.push(node(id2, b[id2].num - a[id2].num));
        }
    }
    // 输出结果
    cout << ans << '\n';
    for (int i = 1; i <= n; i++) if (op[i] == 1) cout << i << ' ';
    cout << '\n';
    for (int i = 1; i <= n; i++) if (op[i] == 2) cout << i << ' ';
    cout << '\n';
    return 0;
}

import java.util.*;
public class Main {
    static class Node {
        int id; long num;
        Node(int id, long num) { this.id = id; this.num = num; }
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), X = sc.nextInt(), Y = sc.nextInt();
        Node[] a = new Node[n + 1];
        Node[] b = new Node[n + 1];
        for (int i = 1; i <= n; i++) a[i] = new Node(i, sc.nextLong());
        for (int i = 1; i <= n; i++) b[i] = new Node(i, sc.nextLong());
        Arrays.sort(a, 1, n + 1, (x, y) -> Long.compare(y.num, x.num));
        long ans = 0;
        int[] op = new int[n + 1]; // 0: 未选, 1: 编程队, 2: 体育队
        for (int i = 1; i <= X; i++) { op[a[i].id] = 1; ans += a[i].num; }
        Arrays.sort(a, 1, n + 1, (x, y) -> Integer.compare(x.id, y.id));
        PriorityQueue<Node> q1 = new PriorityQueue<>((x, y) -> Long.compare(y.num, x.num)); // a_i 最大堆（未选）
        PriorityQueue<Node> q2 = new PriorityQueue<>((x, y) -> Long.compare(y.num, x.num)); // b_i 最大堆（未选）
        PriorityQueue<Node> q3 = new PriorityQueue<>((x, y) -> Long.compare(y.num, x.num)); // (b_i-a_i) 最大堆（已在编程）
        for (int i = 1; i <= n; i++) {
            q1.add(new Node(i, a[i].num));
            q2.add(new Node(i, b[i].num));
            if (op[i] == 1) q3.add(new Node(i, b[i].num - a[i].num));
        }
        for (int cnt = 0; cnt < Y; cnt++) {
            long best = Long.MIN_VALUE; int id1 = -1, id2 = -1; int opt = 0;
            while (!q2.isEmpty() && op[q2.peek().id] != 0) q2.poll();
            if (!q2.isEmpty()) { best = q2.peek().num; id1 = q2.peek().id; opt = 1; }
            while (!q1.isEmpty() && op[q1.peek().id] != 0) q1.poll();
            while (!q3.isEmpty() && op[q3.peek().id] != 1) q3.poll();
            if (!q1.isEmpty() && !q3.isEmpty()) {
                long gain = q1.peek().num + q3.peek().num; // a_j + (b_i - a_i)
                if (gain > best) { best = gain; id1 = q3.peek().id; id2 = q1.peek().id; opt = 2; }
            }
            ans += best;
            if (opt == 1) {
                q2.poll();
                op[id1] = 2;
            } else {
                q1.poll(); q3.poll();
                op[id1] = 2; op[id2] = 1;
                q3.add(new Node(id2, b[id2].num - a[id2].num));
            }
        }
        System.out.println(ans);
        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= n; i++) if (op[i] == 1) sb.append(i).append(' ');
        System.out.println(sb.toString().trim());
        sb.setLength(0);
        for (int i = 1; i <= n; i++) if (op[i] == 2) sb.append(i).append(' ');
        System.out.println(sb.toString().trim());
    }
}

def main():
    import sys
    input = sys.stdin.readline
    n,X,Y = map(int, input().split())
    a = [0] + list(map(int, input().split()))
    b = [0] + list(map(int, input().split()))
    NEG_INF = -10**18
    dp = [[[NEG_INF]*(Y+1) for _ in range(X+1)] for __ in range(n+1)]
    choice = [[[0]*(Y+1) for _ in range(X+1)] for __ in range(n+1)]
    dp[0][0][0] = 0
    for i in range(1, n+1):
        for j in range(X+1):
            for k in range(Y+1):
                dp[i][j][k] = dp[i-1][j][k]
                choice[i][j][k] = 0
                if j>0 and dp[i-1][j-1][k] + a[i] > dp[i][j][k]:
                    dp[i][j][k] = dp[i-1][j-1][k] + a[i]
                    choice[i][j][k] = 1
                if k>0 and dp[i-1][j][k-1] + b[i] > dp[i][j][k]:
                    dp[i][j][k] = dp[i-1][j][k-1] + b[i]
                    choice[i][j][k] = 2
    ans = dp[n][X][Y]
    print(ans)
    P, S = [], []
    i, j, k = n, X, Y
    while i>0:
        if choice[i][j][k] == 1:
            P.append(i)
            j -= 1
        elif choice[i][j][k] == 2:
            S.append(i)
            k -= 1
        i -= 1
    print(*P[::-1])
    print(*S[::-1])

if __name__ == '__main__':
    main()