完美世界 互联网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#