题目链接
题目描述
某校共有 名学生，第
名学生拥有两项能力：编程能力
与体育能力
。即将到来的奥林匹克竞赛包括编程赛道与体育赛道，学校计划组建两支参赛队伍：编程队伍人数恰为
；体育队伍人数恰为
；同一名学生不能同时进入两支队伍。学校的总实力定义为两支队伍实力之和：编程队伍实力为其所有队员编程能力之和；体育队伍实力为其所有队员体育能力之和。请你为学校选择队员，使得总实力最大，并输出一个可行方案。
输入:
- 一行三个正整数：
、
、
，分别表示学生总数、编程队伍人数和体育队伍人数。
- 一行
，表示第
名学生的编程能力。
- 一行
，表示第
输出:
- 第一行输出一个整数，表示最大总实力。
- 第二行输出
到
- 第三行输出
解题思路
我们使用“贪心+优先队列”策略来组建两支队伍：
- 首先按编程能力
降序排序，选出前
op[id]=1），并累加其编程实力到ans。 - 排序后按原编号恢复顺序；构建三种优先队列：
q1：未入编程队学生的小顶堆，按编程能力greater<node>）。q2：未入体育队学生的小顶堆，按体育能力排序。
q3：已入编程队学生的小顶堆，按边际收益排序。
- 重复
- 从
q2中获取当前最大 - 从
q3中获取当前最大边际收益的在编程队员q1中获取最大的未选学生
，交换二者：
（方案2）。
- 比较两种增益，取更大者更新
ans，并维护op数组及各堆状态。
- 从
- 最终
ans即最大总实力，op[id]==1的为编程队，op[id]==2的为体育队。
代码
#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()
算法及复杂度
- 算法：贪心 + 优先队列。
- 时间复杂度：
。
- 空间复杂度：
。
京公网安备 11010502036488号