0078.三国游戏.md

78. 三国游戏

题目链接

贪心，排序

设wi = Ai - Bi - Ci 的含义为经过第 i 件事情后A国的兵力比 B + C 国的总合多的数量，假如 wi > 0 的话，说明A国经历第 i 件事情后兵力大于B C总和。

可以分别计算A，B，C最多经历多少次事件后依旧获胜，然后取最大值即为结果

首先计算出wi，之后给wi排序后累加，当wi <= 0 的时候就说明到了最多事件数，再经历事件就不具备获胜条件了。

C

C++

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e5+10;
int n;
int a[N],b[N],c[N];
int w[N]; //权值数组
int work(int x[],int y[],int z[])
{
    for(int i=0;i<n;i++)
        w[i]=x[i]-y[i]-z[i];
    sort(w,w+n,greater<int>()); //从大到小进行排序
    LL sum=0;
    if(w[0]<=0) return -1;
    for(int i=0;i<n;i++)
    {
        sum+=w[i];
        if(sum<=0) return i;
    }
    
    return n;
}

int main()
{
   cin>>n;
    for(int i=0;i<n;i++) cin>>a[i];
    for(int i=0;i<n;i++) cin>>b[i];
    for(int i=0;i<n;i++) cin>>c[i];
    int res=max({work(a,b,c),work(b,a,c),work(c,b,a)}); //这种初始化列表的方式可以一次性比较多个，c++11新特性
    cout<<res<<endl;
    return 0;
}

Java

import java.util.*;

public class Main {
	
	static int MAX = 100010;
	static int n;
	static int[] w = new int[MAX];
	
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        int[] A = new int[n];
        int[] B = new int[n];
        int[] C = new int[n];
        for (int i = 0; i < n; i++) A[i] = scan.nextInt();
        for (int i = 0; i < n; i++) B[i] = scan.nextInt();
        for (int i = 0; i < n; i++) C[i] = scan.nextInt();
        
        int ans = Math.max(work(C, A, B), Math.max(work(A, B, C), work(B, A, C)));
        System.out.println(ans == 0 ? -1 : ans);
        scan.close();
    }
    
    static int work(int[] X, int[] Y, int[] Z) {
    	for (int i = 0; i < n; i++) {
    		w[i] = X[i] - Y[i] - Z[i];
    	}
    	
    	long sum = 0;
    	// w数组下标区间[0, n - 1]升序排序
    	Arrays.sort(w, 0, n);
        for (int i = n - 1; i >= 0; i--) {
            sum += w[i];
            if(sum <= 0) return n - 1 - i;
        }
        return n;
    }
}

Python

JS

Go