三国游戏

题目

小蓝正在玩一款游戏。
游戏中魏蜀吴三个国家各自拥有一定数量的士兵 X, Y, Z（一开始可以认为都为 0）。

游戏有 n个可能会发生的事件，每个事件之间相互独立且最多只会发生一次，当第 i
个事件发生时会分别让 X, Y, Z增加 \(A_i, B_i, Ci\)
。

当游戏结束时 (所有事件的发生与否已经确定)，如果 X, Y, Z的其中一个大于另外两个之和，我们认为其获胜。

例如，当$ X>Y+Z$时，我们认为魏国获胜。

小蓝想知道游戏结束时如果有其中一个国家获胜，最多发生了多少个事件?

如果不存在任何能让某国获胜的情况，请输出 −1。

输入格式

输入的第一行包含一个整数 n。

第二行包含 n个整数表示 \(A_i\)，相邻整数之间使用一个空格分隔。

第三行包含 n个整数表示 \(B_i\)，相邻整数之间使用一个空格分隔。

第四行包含 n个整数表示 \(C_i\)，相邻整数之间使用一个空格分隔。

输出格式

输出一行包含一个整数表示答案。

数据范围

对于 40%的评测用例，n≤500；
对于 70%的评测用例，n≤5000；
对于所有评测用例，1≤n≤10^5，0≤\(A_i, B_i, Ci\)≤10^9;
注意，蓝桥杯官方给出的关于 \(A_i, B_i, Ci\)的数据范围是 \(1≤A_i,B_i,C_i ≤ 10^9，\)但是这与给出的输入样例相矛盾，因此予以纠正。

样例

3
1 2 2
2 3 2
1 0 7

输入样例1

2

输出样例1

样例解释

发生两个事件时，有两种不同的情况会出现获胜方。

发生 1, 2事件时蜀国获胜。

发生 1, 3事件时吴国获胜。

题解

思路

分类讨论每一个国家作为X，其余作为Y,Z其中之一，没有区别。X > Y + Z
题目要求求最多发生的事件数，在满足X > Y + Z
分类讨论+贪心
分类：把每一个国家看作X，进行求事件数，最后算最大值
贪心：找到一个X，算每一个时刻的对X贡献值大小（X - Y - Z），然后对该贡献值排序，然后累加，进行个数判断，直到累加结果为小于等于0的

代码

#define fi first
#define se second
#define pb push_back
#define ppb pop_back
#define SZ(v) ((int)v.size())
#define int long long
typedef long long ll;
typedef unsigned int u32;
typedef unsigned long long u64;
typedef double db;
using namespace std;
const int N = 1e6;
int _;

int n;
int a[N], b[N], c[N], t[N];

int f(int* x, int* y, int* z) {
    for(int i = 1; i <= n; i++) {
        t[i] = x[i] - y[i] - z[i];
    }
    sort(t+1, t+n+1, greater<int>());
    for(int i = 1; i <= n; i++) {
        t[i] += t[i-1];
        if(t[i] <= 0) return i - 1; 
    }
    return n;
}

void solve() {
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= n; i++) cin >> b[i];
    for(int i = 1; i <= n; i++) cin >> c[i];
    int ans = max({f(a, b, c), f(b, a, c), f(c, a, b)});
    if(ans == 0) {
        cout << "-1\n";
    } else {
        cout << ans << "\n";
    }
}   
 
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); 
    _ = 1;
    // cin >> _;
    while(_--) {
        solve();
    }
    return 0;
}