百度2019秋招筆試真題----------混戰世界

混戰世界

題目描述

戰亂年代，整個世界各個軍閥的兵團混戰，你是某軍團的戰略參謀，你手下有n(保證為3的倍數)個士兵，第i個士兵的實體攻擊數值為Ai，魔法攻擊數值為Bi，你需要将這些士兵三等分為三個連，第一個連需要去實體空間參加實體對抗戰争，戰鬥力估值W1為士兵的實體攻擊數值之和；第二個連需要去魔法空間參加對抗戰争，戰鬥力估值W2為士兵的魔法攻擊數值之和；第三個連需要去虛幻空間參加實體魔法兼備的綜合對抗戰争，戰鬥力估值W3為所有士兵的實體攻擊數值、魔法攻擊數值之和除以2。你希望W1+W2+W3最大，這樣才最有可能勝利。

輸入描述

第一行一個整數n，保證為3的倍數。（3<=n<=100000）

第二行n個整數，第i個數表示Ai

第三行n個整數，第i個數表示Bi（1<=Ai,Bi<=1000）

輸出描述

一個小數，表示最大數值和，保留倆位小數（四舍五入）

輸入樣例

6

1 7 3 4 5 9

2 3 9 4 3 3

輸出樣例

35.00

package Test;

import java.text.DecimalFormat;
import java.util.Arrays;
import java.util.Scanner;

public class test {
	public static void main(String[] args) {
		Scanner s=new Scanner (System.in);
		int n=s.nextInt();
		if(n%3!=0) {
			System.out.println("請重新輸入");
			return ;
		}
		int a1[] =new int[n];  //a1存儲實體攻擊值
		int a2[] =new int[n];	//a2存儲魔法攻擊值
		for(int i=0;i<n;i++) {
			a1[i] =s.nextInt();
		}
		for(int i=0;i<n;i++) {
			a2[i] =s.nextInt();
		}
		solution(n,a1,a2);
	}
	public static  void solution (int n,int a1[],int a2[]) {
		int a3[] =new int [n];
		for(int i=0;i<n;i++ ) {
			a3[i] =a1[i] -a2[i];
		}
		Arrays.sort(a3);  //從小到大排序
		int n1 =n/3;
		int w1=0;
		int w2=0;
		int w3=0;
		for(int i =0;i<n1;i++) {
			for(int j =0;j<n;j++) {
				if(a1[j]-a2[j]==a3[i]) {
					w2 =w2+a2[j];
				}
			}
		}
		for(int i =n1;i<2*n1;i++) {
			for(int j =0;j<n;j++) {
				if(a1[j]-a2[j]==a3[i]) {
					w3 =w3+(a1[j]+a2[j])/2;
				}
			}
		}
		for(int i =2*n1;i<3*n1;i++) {
			for(int j =0;j<n;j++) {
				if(a1[j]-a2[j]==a3[i]) {
					w1 =w1+a1[j];
				}
			}
		}
		int w=w1+w2+w3;
		DecimalFormat df =new DecimalFormat ("#.00");
		System.out.println(df.format(w));
				}
}
           

解題思路：

因為要保證n為3的倍數，是以在輸入的時候要對n進行判斷，a1，a2，a3 數組分别存儲實體攻擊值、魔法攻擊值、和實體-魔法的值，對a3數組進行排序，值越大說明實體值越大，放到一連；值越小說明魔法值越大，放到二連；剩下的放到三連，這樣使得一二三連總和攻擊值最大。最後循環a3數組，找到在a1，a2中的索引，進行計算