蓝桥杯真题 - 三国游戏 - 题解

题目链接：https://www.lanqiao.cn/problems/3518/learning/

个人评价：难度 2 星（满星：5）
前置知识：贪心

整体思路

• 先假设魏蜀吴中的某一个势力最终获胜的情况下，如何求出事件发生的最大数量，最后枚举三个势力获胜的情况取最大值就是答案；
• 假设魏国最终胜利，那最好是让已发生的事件中 $A_i$ 的和尽可能大于 $B_i+C_i$ 的和，大得越多越优先选择让这个事件发生，所以按 $A_i-B_i-C_i$ 从大到小排序，依次选择需要发生的事件即可，选到 $A_i$ 的和小于等于 $B_i+C_i$ 的和就不再选了。

过题代码

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
const int maxn = 100000 + 100;
int n;
LL x[maxn], y[maxn], z[maxn];
LL a[maxn], b[maxn], c[maxn];

int solve(LL num[maxn]) {
    if (num[n - 1] <= 0) {
        return -1;
    }
    LL tmp = 0;
    for (int i = n - 1; i >= 0; --i) {
        tmp += num[i];
        if (tmp <= 0) {
            return n - i - 1;
        }
    }
    return  n;
}

int main(){
#ifdef ExRoc
    freopen("test.txt", "r", stdin);
#endif // ExRoc
    ios::sync_with_stdio(false);

    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> x[i];
    }
    for (int i = 0; i < n; ++i) {
        cin >> y[i];
    }
    for (int i = 0; i < n; ++i) {
        cin >> z[i];
    }
    for (int i = 0; i < n; ++i) {
        a[i] = x[i] - y[i] - z[i];
        b[i] = y[i] - x[i] - z[i];
        c[i] = z[i] - x[i] - y[i];
    }
    sort(a, a + n);
    sort(b, b + n);
    sort(c, c + n);
    cout << max({solve(a), solve(b), solve(c)}) << endl;

    return 0;
}