CF730I Olympiad in Programming and Sports 题解

题目链接：Olympiad in Programming and Sports

题意：

有 \(n\) 个学生每人有两种技能，分别是 \(a,b\) 表示编程能力和运动能力。你需要将他们分为两个团队分别参加编程比赛和体育比赛，编程团队有 \(p\) 人，体育团队有 \(s\) 人，一个学生只能参加其中一项。每个团队的力量是其成员在对应领域能力总和，请问如何分配能使得两个团队的实力和最大？

输入格式

共三行，第一行包含三个正整数 \(n,p,s\)。

第二行有 \(n\) 个整数 \(a_1,a_2\cdots a_n\)，第三行，有 \(n\) 个整数\(b_1,b_2\cdots b_n\)。

输出格式

第一行输出整个团队最大的实力，然后给出一种构造方案即可。

数据范围：

\(2\le n\le 3\times 10^3,~1\le p+s\le n,~1\le a_i,b_i\le 3000\)。

经典的多个堆维护反悔贪心。做完这题可以去做一下 CF436E 和 P5470

考虑将最大的 \(p\) 个人先选到 \(a\) ，然后通过反悔贪心凑满 \(s\) 个人进到 \(b\)。

每次决策有两种情况：

1. 将一个没选过的人扔到 \(b\) ，贡献为 \(b_i\) 。
2. 将一个 \(a\) 的人扔到 \(b\) ，再找另一个人到 \(a\) ，贡献为 \(b_i - a_i + a_j\) 。

考虑用三个大根堆维护 \(a_i,b_i,b_i-a_i\) 即可。

时间复杂度 \(\mathcal{O}(n \log n)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define N ((int)(1e5 + 15))

int n, A, B, res, type[N];
struct node { int x, i; } a[N], b[N];
bool operator<(const node &x, const node &y) { return x.x > y.x; }
bool operator>(const node &x, const node &y) { return x.x < y.x; }
struct qwq
{
    int op; priority_queue< node, vector<node>, greater<node> > q;
    void up(){ while(!q.empty() && type[q.top().i] != op) q.pop(); }
    void push(const node &x) { q.push(x); }
    node top() { up(); return q.top(); }
    bool empty() { up(); return q.empty(); }
    void clear() { op = 0; q = {}; }
} q1, q2, q3;
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> A >> B; q1.op = 0, q2.op = 0, q3.op = 1;
    rep(i, 1, n) { cin >> a[i].x, a[i].i = i; }
    rep(i, 1, n) { cin >> b[i].x, b[i].i = i; }
    sort(a + 1, a + 1 + n);
    rep(i, 1, A) { res += a[i].x, type[a[i].i] = 1; }
    sort(a + 1, a + 1 + n, [](node x, node y) { return x.i < y.i; });
    rep(i, 1, n)
    { 
        q1.push({a[i].x, i});
        q2.push({b[i].x, i}); q3.push({b[i].x - a[i].x, i});
    }
    rep(awa, 1, B)
    {
        int op = -1, x, i, j, mx = -INF;
        if(!q2.empty() && (x = q2.top().x) > mx) { mx = x; op = 1; i = q2.top().i; }
        if(!q3.empty() && !q1.empty() && (x = q3.top().x + q1.top().x) > mx)
            { mx = x; op = 2; i = q3.top().i; j = q1.top().i; }
        res += mx;
        if(op == 1) { type[i] = 2; }
        else if(op == 2) { type[i] = 2; type[j] = 1; q3.push({b[j].x - a[j].x, j}); }
    }
    cout << res << '\n';
    rep(i, 1, n) if(type[i] == 1) { cout << i << ' '; } cout << '\n';
    rep(i, 1, n) if(type[i] == 2) { cout << i << ' '; } cout << '\n';
    return 0;
}

---

参考文献：

[1] https://www.luogu.com.cn/article/xyilo2dv