4.14 完美世界笔试凉凉 只有2AC
感觉这次笔试不是很难，但是奈何做的题太少，还是有俩到没做出来 哎。。。
第一题：求承载所有人做少需要的船数量
看到这道题第一个给我的直觉就像是跟二数之和相似的思路。想达到最少的船数量，最好的办法就是一个小的体重匹配一个大的体重，因为如果俩个小体重的人坐一个船，就浪费了很多承载空间。
所以按照这个思路，先排序，然后定义俩个指针，左指针指向第一位，右指针指向最后一位，然后相加，sum 大于 limit,说明这俩个人无法坐一个穿，所以就把右指针向左移动一位，因为如果移动左指针，只会使得sum更大。如果sum < = limit, 说明这俩个人可以坐一个船，于是标志这俩人已经被承载，并且把右指针往左移动一位，左指针往右移动一位。重复以上循环直到左指针不比右指针小。
代码如下：
package Testing;
import java.util.*;
import javax.xml.soap.Node;
public class Main
{
public static void main(String [] args)
{
Scanner scan = new Scanner(System.in);
String input= scan.nextLine();
int limit = Integer.parseInt(scan.nextLine());
String [] weightArr = input.split(" ");
int [] weights = new int[weightArr.length];
for(int i = 0; i < weightArr.length; i++)
{
weights[i] = Integer.parseInt(weightArr[i]);
}
Arrays.sort(weights);
int[] mark = new int[weightArr.length];
int left = 0;
int right = weights.length - 1;
int minimum = 0;
while(left < right)
{
int first = weights[left];
int second = weights[right];
int sum = first + second;
if(sum <= limit)
{
mark[left] = 1;
mark[right] = 1;
left++;
right--;
minimum++;
}
else
right--;
}
for(int result : mark)
{
if(result == 0)
minimum++;
}
System.out.print(minimum);
}
} 第二题：典型的最短路径题，然而做的时间太久，忘记怎么做了。。。哎痛苦 第三题：纸盒嵌套问题：感觉挺难的不会，但是思路我觉得大概是要按照长先排序，然后进一步操作，还请各位大佬分享一些思路。
第四题：这题背过，是背包问题，用DP解，不难
代码如下：
package Testing;
import java.util.*;
import javax.xml.soap.Node;
public class Main
{
public static void main(String [] args)
{
Scanner scan = new Scanner(System.in);
int number = scan.nextInt();
int capacity = scan.nextInt();
int[] weight = new int[number + 1];
int[] value = new int[capacity + 1];
int[][] dp = new int[number + 1][capacity + 1];
for(int i = 1; i < number; i++)
weight[i] = scan.nextInt();
for(int i = 1; i < number ; i++)
value[i] = scan.nextInt();
for(int i = 1; i <= number; i++)
{
for(int j = 0; j <= capacity; j++)
{
dp[i][j] = dp[i - 1][j];
if(j >= weight[i])
{
dp[i][j] = Math.max(dp[i][j], dp[i -1][j - weight[i] + value[i]]);
}
}
}
int max = 0;
for(int i = 0; i <= number; i++)
{
max = Math.max(max, dp[number][i]);
}
System.out.print(max);
}
} 
查看9道真题和解析
