完美世界互联网JAVA笔经

选择十题

多选五题

编程四题，留的时间大概一小时余一些

1.几个人坐船过河，船有载重，最少用几条船。

暴力只A了80%...

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class ques1 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s=br.readLine();
        String []str1=s.split(" ");
        int []weights=new int[str1.length];
        for(int i=0;i<str1.length;i++){
            weights[i]=Integer.parseInt(str1[i]);
        }
        int maxLoad=Integer.parseInt(br.readLine());
        int n=str1.length;
        int count=0;

        for(int i=0;i<n;i++){
            int total=0;
            for(int j=0;j<n;j++){
                int num=0,weight=0;

                for(int x=0;x<n;x++){
                    if(weights[x]!=0){
                        if(weight<weights[x]&&total+weights[num]<=maxLoad){
                            weight=weights[x];
                            num=x;
                        }
                    }
                }
                if(total+weights[num]<=maxLoad){
                    total+=weights[num];
                    weights[num]=0;
                }
            }
            if(total!=0)
                count++;
        }
        if (count==0)
            System.out.println(1);
        else
            System.out.println(count);
    }
}

2.有向图求起始点到各点最短距离

import java.util.Scanner;

public class ques2 {
    public static void main(String[] args) {
        int[][] weight=new int[6][];
        String[] pointsStr={"V1","V2","V3","V4","V5"};
        Scanner input=new Scanner(System.in);
        for(int i=0;i<pointsStr.length;i++){
            String[] valuesStr=input.nextLine().split(" ");
            int[] values=new int[valuesStr.length];
            for (int j=0;j<valuesStr.length;j++){
                values[j]=Integer.parseInt(valuesStr[j]);
            }
            weight[i]=values;
        }
        input.close();

        for(int i=0;i<5;i++){
            for(int j=0;j<5;j++){
                if(weight[i][j]==-1)
                    weight[i][j]=9999;
            }
        }

        for(int a=0;a<5;a++){
            for(int i=0;i<5;i++){
                for(int j=0;j<5;j++){
                    for(int x=0;x<5;x++){
                        if(weight[i][x]>weight[i][j]+weight[j][x]){
                            weight[i][x]=weight[i][j]+weight[j][x];
                        }
                    }
                }
            }
        }

        System.out.println(weight[0][1]);
        System.out.println(weight[0][2]);
        System.out.println(weight[0][3]);
        System.out.println(weight[0][4]);
    }
}

3.n个有长度和宽度的盒子，不可旋转，问最多套几层

import java.util.Scanner;

public class ques3 {
    public static void main(String[] args) {
        Scanner in=new Scanner(System.in);
        int x=in.nextInt();
        int [][]array=new int[x][2];
        for(int i=0;i<x;i++){
            for(int j=0;j<2;j++){
                array[i][j]=in.nextInt();
            }
        }
        int [] num=new int [x];
        for(int i=0;i<x;i++){
            num[i]=1;
        }
        for(int a=0;a<x;a++){
            for(int i=0;i<x;i++){
                for(int j=0;j<x;j++){
                    if(array[i][0]>array[j][0]&&array[i][1]>array[j][1]){
                        num[i]=Math.max(num[j]+1,num[i]);
                    }
                }
            }
        }
        int count=0;
        for(int i=0;i<x;i++){
            count=Math.max(count,num[i]);
        }
        System.out.println(count);
    }
}

4.01背包

import java.util.Scanner;

public class ques4 {
    public static void main(String[] args) {
        Scanner in=new Scanner(System.in);
        int n;
        int weight;
        n=in.nextInt();
        weight=in.nextInt();
        int []w=new int[n];
        int []v=new int[n];
        for(int i=0;i<n;i++){
            w[i]=in.nextInt();
        }
        for(int i=0;i<n;i++){
            v[i]=in.nextInt();
        }

        int[] dp=new int [10010];
        for(int i=0;i<dp.length;i++)
            dp[i]=0;

        for(int i=0;i<n;i++){
            for(int j=weight;j>=w[i];j--){
                dp[j] = Math.max(dp[j],dp[j-w[i]]+v[i]);
            }
        }
        int x=0;
        for(int i=0;i<10010;i++){
            x=Math.max(x,dp[i]);
        }
        System.out.println(x);
    }
}

时间太紧了，剩半分钟写完，交卷时还剩五秒🤣🤣

#完美世界##校招##笔经##春招##Java#