完美世界校招算法题2018

题目一

首先输入一个整数n

有A、B两个队伍，每个队伍有n个人，每个人都有一个整数型武力值，

A队,B队每个人相互比武，武力值大,队伍+100，相等不加分，武力值小-100。每个人只出场一次。输出A队最高得分

输入样例

6

2 3 4 5 6 7

3 4 5 6 7 8

输出

200

import java.util.Arrays;
import java.util.Scanner;

/**
* Created by 95112 on 11/1/2017.
*/
public class PK {
   public static void main(String[] args)
   {
       Scanner scanner = new Scanner(System.in);
       int n = scanner.nextInt();
       long[] A = new long[n];
       long[] B = new long[n];
       for (int i =0 ; i< n ; i++)
           A[i] = scanner.nextLong();
       for (int i= 0 ; i <n ;i++)
           B[i] = scanner.nextLong();
       boolean[] Bused = new boolean[n];
       boolean[] Aused = new boolean[n];
       int sum = 0 ;
       Arrays.sort(A);
       Arrays.sort(B);
       int count = 0;
       for (int i = n-1 ; i>=0 ; i-- ){
           for (int j = n-1 ; j>= 0 ; j--){
               if (Bused[j])
                   continue;
               if (A[i] == B[i])
                   break;
               if (A[i] > B[j]){
                   Aused[i] = true;
                   sum += 100;
                   Bused[j] = true;
                   count++;
                   break;
               }

           }
       }
       for (int i = n -1 ; i>=0 ; i--) {
           if (Aused[i])
               continue;
           for (int j = n-1; j >= 0; j--) {
               if (Bused[j])
                   continue;
               if (A[i] > B[j]){
                   Aused[i] = true;
                   sum += 100;
                   Bused[j] = true;
                   count++;
                   break;
               }
               if (A[i] == B[j]) {
                   Aused[i] = true;
                   Bused[j] = true;
                   count++;
                   break;
               }
           }
       }
       sum = sum - (n - count)*100;
       System.out.println(sum);
   }
}
/*
6
2 3 4 5 6 7
3 4 5 6 7 8

4
9 7 5 3
10 8 5 2
*/

题目二

小明解数学题，输入n表示有n道题，然后第二行输入每道题的分数，第三道题输入每道题所花时间，第四行输入 总共的考试时间。输出最高分数。

import java.util.Scanner;

/**
* Created by 95112 on 11/1/2017.
*/
public class Math {
   public static void main(String[] args)
   {
       Scanner scanner = new Scanner(System.in);
       int amount = scanner.nextInt();
       int[] scores = new int[amount];
       int[] spentTime = new int[amount];
       for (int i = 0 ; i< amount;i++)
           scores[i] = scanner.nextInt();
       for (int i =0 ; i < amount ; i++)
           spentTime[i] = scanner.nextInt();
       int Time = scanner.nextInt();
       int[] dp = new int[Time+1];
       for (int i = 0 ;  i< amount; i++)
       {
           for (int j = Time ; j >=0 ; j--){
               if ( j >= spentTime[i]){
                   dp[j] = max(dp[j] , dp[j - spentTime[i]] + scores[i]);
               }
           }
       }
       System.out.println(dp[Time]);
   }
   private static int max(int a, int b)
   {
       if (a > b)
           return a;
       else
           return b;
   }
}
/*
5
5 4 3 5 2
2 2 3 5 1
10
*/