完美世界校招在线笔试题-互联网Java（11月1日）编程题

野性酷女 2022-06-06 06:56 268阅读 0赞

## 一、题目 ##

考试题目数为n，每道题只有做和不做。每道题都有不同难度，且每道题都各自分值及完成所需时间。现在计算在给定的时间m内，做题的最大得分。

输入：

第一行 ：n 代表题目数

第二行：n个题目，每道题的分值

第三行：n个题目，完成所需时间

第四行：考试给定的时间m

输出：

最大得分

解析：

背包问题，参考 [http://www.cnblogs.com/lfeng1205/p/5981198.html][http_www.cnblogs.com_lfeng1205_p_5981198.html]

下面是AC源码

import java.util.*;
    
    public class Main4{
    	
        public static void main(String args[]){
        	
            Scanner sc = new Scanner(System.in);
            
            int n = sc.nextInt();
            int[] a = new int[n];
            int[] b = new int[n];
            
            for(int i = 0; i < 2; i++){
                for(int j = 0; j < n; j++){
                    if(i==0){
                        a[j] = sc.nextInt();
                    }else{
                    	b[j] = sc.nextInt();
                    }
                }
            } 
            int m =  sc.nextInt();
            int c[][] = bk(m, n, b, a);
            
           System.out.println(c[n][m]);
        }
        
        public static int[][] bk(int m, int n, int[] w, int[] p) {
            int c[][] = new int[n + 1][m + 1];
            for (int i = 0; i < n + 1; i++)
                c[i][0] = 0;
            for (int j = 0; j < m + 1; j++)
                c[0][j] = 0;
    
            for (int i = 1; i < n + 1; i++) {
                for (int j = 1; j < m + 1; j++) {
                    if (w[i - 1] <= j) {
                        if (c[i - 1][j] < (c[i - 1][j - w[i - 1]] + p[i - 1]))
                            c[i][j] = c[i - 1][j - w[i - 1]] + p[i - 1];
                        else
                            c[i][j] = c[i - 1][j];
                    } else
                        c[i][j] = c[i - 1][j];
                }
            }
            return c;
        }
    }

##  二、题目 ##

A,B两个队伍比赛，每队各有n个队员，每个队员都有自己的战力值（>0）。每次每队选1名参赛，且每名只能比一次，武力值大的获胜（相等则平局）。赢一局队伍得100金币，输一局扣100金币，平局不扣不加。现在计算A队的最大可获得金币。

**输入：**

第一行 ：n 代表每队n个队员

第二行：A队每个成员的战力值

第三行：B队每个成员的战力值

** 输出：**

A队的最大可获得金币

例如：

输入

9 7 5 3

10 8 5 2

输出

200

**解析：**

输入的数据，2个数组，应该都是有序递减的。A队要获得金币最大，获胜次数尽可能多。有点像田忌赛马，也就是：A中每个元素，和B中一个最邻近的且是大于B的元素值去比赛，这样获胜次数才能最多。

下面是我当时提交的:

package wanmei;
    
    import java.util.Scanner;
    
    public class Main {
    	
    	static int sameNum = 0;
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            
            int n = sc.nextInt();
            int ans = 0;
            int[] a = new int[n];
            int[] b = new int[n];
            
            for(int i = 0; i < 2; i++){
                for(int j = 0; j < n; j++){
                    if(i==0){
                        a[j] = sc.nextInt();
                    }else{
                    	b[j] = sc.nextInt();
                    }
                    
                }
            } 
            
            for (int i = 0; i < n; i++) {
            	int c = find(b ,n,  a[i]);
            	
    			if(c >0){
    				ans++;
    				if(c == 2222){
    					break;
    				}
    			}
    		}
            System.out.println(ans*100-(n-ans)*100);
        }
        
        
        static int  find(int a[],int n,int x){//b ,4 ,9
            int min= Math.abs(a[0] - x);
            int r=-1;
         
            for(int i=0; i < n;++i){
            	if(x < a[i]){
            		continue;
            	}else if(x== a[i]){
            		sameNum++;
            	}else{
            		if(i==n-1){
            			r=2222;
                		break;
            		}
            		r=i;
            		break;
            	}
            }
            return r;
        }
    }

只通过40%的case，后来想想，是平局的没计算好。关于平局的，想了很多种情形，感觉有点复杂。比如：

A队： 5  4  2  1

B队：4  3  2  1

A胜2平2

A队： 7  5  3  1

B队：8  5  2  1

A胜3负1

A队： 4  3  1

B队：3  2  1

A胜2平1

现在想到的就是把a,b数组在存到*listA*，*listB * 里面，把参赛过的元素去除，则最后*listA*中剩下的都是*<= listB * 元素的，再算平局数。

[http_www.cnblogs.com_lfeng1205_p_5981198.html]: http://www.cnblogs.com/lfeng1205/p/5981198.html