題目描述
小藍正在玩一款游戲，游戲中魏蜀吳三個國家各自擁有一定數量的士兵X, Y, Z (一開始可以認為都為 0 )，游戲有 n 個可能會發生的事件，每個事件之間相互獨立且最多只會發生一次，當第 i 個事件發生時會分別讓 X, Y, Z 增加Ai , Bi ,Ci ，
當游戲結束時 (所有事件的發生與否已經確定)，如果 X, Y, Z 的其中一個大于另外兩個之和，我們認為其獲勝，例如，當 X > Y + Z 時，我們認為魏國獲勝，小藍想知道游戲結束時如果有其中一個國家獲勝，最多發生了多少個事件?
如果不存在任何能讓某國獲勝的情況，請輸出 ?1 ，
輸入格式
輸入的第一行包含一個整數 n ，
第二行包含 n 個整數表示 Ai，相鄰整數之間使用一個空格分隔，
第三行包含 n 個整數表示 Bi，相鄰整數之間使用一個空格分隔，
第四行包含 n 個整數表示 Ci，相鄰整數之間使用一個空格分隔，
輸出格式
輸出一行包含一個整數表示答案，
樣例輸入
3
1 2 2
2 3 2
1 0 7
樣例輸出
2
解答
1.解題思路是，使用貪心思想選出三個國家各自獲勝的最大事件數，取其最大作為答案；
那么如何算出一個國家士兵應該經歷哪些事件并滿足大于另外兩國呢，同樣使用貪心演算法
2.我們使用一個類來存盤一個事件，這個事件有abc三個屬性，分別對應題目對三個國家兵力的提升
static class node {
long a, b, c;
public node(long a, long b, long c) {
this.a = a;
this.b = b;
this.c = c;
}
}
那么我們輸入資料時需要注意一點，它的每一行都是對一個國家的影響，也就是對于事件i，輸入的第一行資料是事件i的a,第二行資料才是事件i的b
node[] events = new node[n];
for (int i = 0; i < n; i++) events[i] = new node(sc.nextInt(), 0, 0);
for (int i = 0; i < n; i++) events[i].b = sc.nextInt();
for (int i = 0; i < n; i++) events[i].c = sc.nextInt();
3.我們對事件進行排序，排序規則根據我們的需求而定，我們需要得出每個國家獲勝的事件數，就把事件排序為對那個國家提升的兵力最多的事件最靠前
比如
1 2 2
2 3 2
1 0 7
事件i1對第一個國家提升量為-2，而i2提升量為-1，i3提升量為-7，則排序為i2i1i3
事件i1對第二個國家提升量為0，而i2提升量為1，i3提升量為-7，則排序為i2i1i3
事件i1對第三個國家提升量為-2，而i2提升量為-5，i3提升量為3，則排序為i3i1i2
Arrays.sort(events, (o1, o2) -> o2.a - o2.b - o2.c + o1.b + o1.c - o1.a > 0 ? 1 : -1);
Arrays.sort(events, (o1, o2) -> o2.b - o2.a - o2.c + o1.a + o1.c - o1.b > 0 ? 1 : -1);
Arrays.sort(events, (o1, o2) -> o2.c - o2.a - o2.b + o1.a + o1.b - o1.c > 0 ? 1 : -1);
排序完之后使用排序后的順序算出對應國家在最大優勢的情況下可以經過幾個事件并滿足兵力大于其他兩國
Arrays.sort(events, (o1, o2) -> o2.a - o2.b - o2.c + o1.b + o1.c - o1.a > 0 ? 1 : -1);
ans = Math.max(ans, f(events, 0));
Arrays.sort(events, (o1, o2) -> o2.b - o2.a - o2.c + o1.a + o1.c - o1.b > 0 ? 1 : -1);
ans = Math.max(ans, f(events, 1));
Arrays.sort(events, (o1, o2) -> o2.c - o2.a - o2.b + o1.a + o1.b - o1.c > 0 ? 1 : -1);
ans = Math.max(ans, f(events, 2));
這里使用一個數字標記當前優勢國，而且如果你不能在第一個事件就大于其他兩國，那么后面就更不可能了，所以不滿足a>b+c時就直接break并回傳事件數
private static long f(node[] events, int cur) {
long a = 0, b = 0, c = 0;
long res = 0;
for (int i = 0; i < events.length; i++) {
a += events[i].a;
b += events[i].b;
c += events[i].c;
if (cur == 0) {
if (a > b + c) {
res = i + 1;
} else {
break;
}
} else if (cur == 1) {
if (b > a + c) {
res = i + 1;
} else {
break;
}
} else {
if (c > b + a) {
res = i + 1;
} else {
break;
}
}
}
return res;
}
4.最后列印答案，如果事件數為0，說明沒有國家能夠滿足a>b+c的條件列印-1即可
System.out.println(ans == 0 ? -1 : ans);
完整代碼
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
long ans = 0;
node[] events = new node[n];
for (int i = 0; i < n; i++) events[i] = new node(sc.nextInt(), 0, 0);
for (int i = 0; i < n; i++) events[i].b = sc.nextInt();
for (int i = 0; i < n; i++) events[i].c = sc.nextInt();
Arrays.sort(events, (o1, o2) -> o2.a - o2.b - o2.c + o1.b + o1.c - o1.a > 0 ? 1 : -1);
ans = Math.max(ans, f(events, 0));
Arrays.sort(events, (o1, o2) -> o2.b - o2.a - o2.c + o1.a + o1.c - o1.b > 0 ? 1 : -1);
ans = Math.max(ans, f(events, 1));
Arrays.sort(events, (o1, o2) -> o2.c - o2.a - o2.b + o1.a + o1.b - o1.c > 0 ? 1 : -1);
ans = Math.max(ans, f(events, 2));
System.out.println(ans == 0 ? -1 : ans);
}
private static long f(node[] events, int cur) {
long a = 0, b = 0, c = 0;
long res = 0;
for (int i = 0; i < events.length; i++) {
a += events[i].a;
b += events[i].b;
c += events[i].c;
if (cur == 0) {
if (a > b + c) {
res = i + 1;
} else {
break;
}
} else if (cur == 1) {
if (b > a + c) {
res = i + 1;
} else {
break;
}
} else {
if (c > b + a) {
res = i + 1;
} else {
break;
}
}
}
return res;
}
static class node {
long a, b, c;
public node(long a, long b, long c) {
this.a = a;
this.b = b;
this.c = c;
}
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/551463.html
標籤：其他
下一篇：返回列表