4965. 三國游戲 - AcWing題庫

小藍(lán)正在玩一款游戲。

游戲中魏蜀吳三個(gè)國家各自擁有一定數(shù)量的士兵?X,Y,Z（一開始可以認(rèn)為都為?00）。

游戲有?n?個(gè)可能會(huì)發(fā)生的事件，每個(gè)事件之間相互獨(dú)立且最多只會(huì)發(fā)生一次，當(dāng)?shù)?i個(gè)事件發(fā)生時(shí)會(huì)分別讓?X,Y,Z增加?Ai,Bi,Ci

當(dāng)游戲結(jié)束時(shí) (所有事件的發(fā)生與否已經(jīng)確定)，如果?X,Y,Z 的其中一個(gè)大于另外兩個(gè)之和，我們認(rèn)為其獲勝。

例如，當(dāng)?X>Y+Z?時(shí)，我們認(rèn)為魏國獲勝。

小藍(lán)想知道游戲結(jié)束時(shí)如果有其中一個(gè)國家獲勝，最多發(fā)生了多少個(gè)事件?

如果不存在任何能讓某國獲勝的情況，請輸出??1。

輸入格式

輸入的第一行包含一個(gè)整數(shù)?n。

第二行包含?n?個(gè)整數(shù)表示?Ai，相鄰整數(shù)之間使用一個(gè)空格分隔。

第三行包含?n?個(gè)整數(shù)表示?Bi，相鄰整數(shù)之間使用一個(gè)空格分隔。

第四行包含?n?個(gè)整數(shù)表示?Ci，相鄰整數(shù)之間使用一個(gè)空格分隔。

輸出格式

輸出一行包含一個(gè)整數(shù)表示答案。

數(shù)據(jù)范圍

對于?40%40%?的評測用例，n≤500≤500；
對于?70%70%?的評測用例，n≤5000≤5000；
對于所有評測用例，1≤n≤105，0≤Ai,Bi,Ci≤109? ? ? ??

輸入樣例：

3
1 2 2
2 3 2
1 0 7

輸出樣例：

2

樣例解釋

發(fā)生兩個(gè)事件時(shí)，有兩種不同的情況會(huì)出現(xiàn)獲勝方。

發(fā)生?1,21,2?事件時(shí)蜀國獲勝。

發(fā)生?1,31,3?事件時(shí)吳國獲勝。

貪心題。要使得國家獲勝 X>Y+Z,就是使得X-Y-Z>0,然后需要求最大發(fā)生事件數(shù)，就是把?X-Y-Z>0 的結(jié)果排序，然后把結(jié)果相加得到sum，使得sum不小于0，此時(shí)就是最大發(fā)生事件數(shù)。

根據(jù)題目提示，因?yàn)?≤Ai,Bi,Ci≤109，所以sum的值很可能會(huì)爆int，所以使用long long。

AC code:

#include<bits/stdc++.h>
using namespace std;
int n;
int ans = 0;
int s[100010];
int a[100010], b[100010], c[100010];
void check(int *a1, int *b1, int *c1) {for (int i = 1; i <= n; i++) s[i] = a1[i] - b1[i] - c1[i];sort(s + 1, s + 1 + n);long long sum = 0;int cnt = 0;for (int i = n; i >= 1; i--) {sum += s[i];if (sum <= 0) {break;}cnt++;}
//	cout << cnt << endl;ans = max(ans, cnt);}
int main() {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] ;}check(a, b, c);check(b, a, c);check(c, b, a);cout << (ans == 0 ? -1 : ans);}