题目描述
难度分:2000
输入n(2≤n≤3000),p,s(p≥1,s≥1,p+s≤n)和长为n的数组a(1≤a[i]≤3000),长为n的数组b(1≤b[i]≤3000)。
有n名学生,第i名学生的编程能力为a[i],运动能力为b[i]。
你需要组建两支队伍:有p人的编程队,有s人的运动队。一个学生不能同时参加两支队伍。
这p+s人的能力值之和最大是多少?学生i 如果在编程队,他的能力值是a[i];如果在运动队,他的能力值是b[i]。
输出最大能力值之和,编程队的学生编号,运动队的学生编号。学生编号从1开始。多解输出任意一解。
输入样例1
5 2 2
1 3 4 5 2
5 3 2 1 4
输出样例1
18
3 4
1 5
输入样例2
4 2 2
10 8 8 3
10 7 9 4
输出样例2
31
1 2
3 4
输入样例3
5 3 1
5 2 5 1 7
6 3 1 6 3
输出样例3
23
1 3 5
4
算法
反悔贪心
先将所有人封装成三元组(编程能力,运动能力,编号)数组tup,按照编程能力降序排列。用编程能力最大的p名学生组成编程队,放入到大根堆pq中,其中存二元组(运动能力-编程能力,编号),然后一个人一个人地构建运动队。准备两个有序集合,rp存剩下学生二元组(编程能力,编号),rs存剩下学生二元组(运动能力,编号)。即维护以下三个数据结构:
- rp: 剩余学生中的编程能力值。
- rs: 剩余学生中的运动能力值。
- pq: 编程队中的【运动能力-编程能力】值。
有两种情况:
- 直接从剩余学生中,选择运动能力最大的。
- 从编程队中调一个【运动能力-编程能力】最大的学生到运动队,然后剩余学生中招一个编程能力最强的人进编程队。
上面这两种方法,哪种能让能力总和变得更大,就用哪种方法,直到运动队的人数够s人。
复杂度分析
时间复杂度
对tup数组排序的时间复杂度为O(nlog2n)。构建初始编程队的时候把编程能力最强的p个人插入大根堆就行,时间复杂度为O(plog2p)。招募s个运动队的成员,每次都要对有序集合进行删除操作,还需要对大根堆进行插入操作,时间复杂度是O(log2s+log2p)的。因此构建编程队的时间复杂度为O(plog2p),构建运动队的时间复杂度为O(s(log2s+log2p)),瓶颈其实是最开始的排序,时间复杂度为O(nlog2n)。
空间复杂度
三元组数组tup,两个大根堆,两个有序集合的空间消耗都是线性的,因此算法的额外空间复杂度为O(n)。
C++ 代码
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 3010;
int n, p, s, a[N], b[N];
int main() {
scanf("%d%d%d", &n, &p, &s);
for(int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
}
for(int i = 1; i <= n; i++) {
scanf("%d", &b[i]);
}
vector<array<int, 3>> tup;
for(int i = 1; i <= n; i++) {
tup.push_back({a[i], b[i], i});
}
// 按编程能力排序
sort(tup.begin(), tup.end(), [&](auto& x, auto& y) {
return x[0] > y[0];
});
priority_queue<PII> pq, sq;
int tot = 0;
for(int i = 0; i < p; i++) {
tot += tup[i][0];
pq.push({tup[i][1] - tup[i][0], tup[i][2]}); // (运动能力-编程能力,编号)
}
set<PII> rp, rs;
for(int i = p; i < n; i++) {
rp.insert({tup[i][0], tup[i][2]});
rs.insert({tup[i][1], tup[i][2]});
}
// 两个队还没满就持续招人
int cnt = 0;
while(sq.size() < s) {
auto ts = *rs.rbegin(); // 剩余运动能力最强的
auto tp = *rp.rbegin(); // 剩余编程能力最强的
auto tpq = pq.top(); // 编程队中 运动能力-编程能力 最大的
if(tot + tpq.first + a[tp.second] > tot + ts.first) {
// 从编程队挖人
tot += tpq.first + a[tp.second];
sq.push({b[tpq.second], tpq.second}); // tpq.second被挖到运动队
pq.pop();
pq.push({b[tp.second] - a[tp.second], tp.second}); // tp.second被加入到编程队
rp.erase({a[tp.second], tp.second});
rs.erase({b[tp.second], tp.second});
}else {
// 从剩余选手中直接招人
tot += b[ts.second];
sq.push({b[ts.second], ts.second});
rp.erase({a[ts.second], ts.second});
rs.erase({b[ts.second], ts.second});
}
}
printf("%d\n", tot);
while(!pq.empty()) {
printf("%d ", pq.top().second);
pq.pop();
}
puts("");
while(!sq.empty()) {
printf("%d ", sq.top().second);
sq.pop();
}
puts("");
return 0;
}