华为机试4.13
第一题
硬件资源分配
有M台服务器，每台服务器有以下属性：编号、CPU核数（1~100）、内存、CPU架构（0~8）、是否支持NP加速的标识（0,1）。然后有一个资源分配要求，要求分配N台满足要求的服务器。具体如下：CPU核数>=cpuCount、内存>=memSize、CPU架构=cpuArch、是否支持NP加速=supportNP。其中，cpuCount、memSize、cpuArch、supportNP为这个要求输入的分配参数。分配时会指定优先级策略，策略如下：
策略1：CPU优先，优先选择CPU核数满足分配要求并且最接近分配要求的cpuCount。如果CPU核数相同，在按内存满足要求并选择最接近memSize的服务器分配。
策略2：内存优先，优先选择内存满足分配要求并且最接近分配要求的memSize。如果内存相同，在按cpu核数满足要求并选择最接近cpuCount的服务器分配
如果两台服务器属性都相同，则按服务器编号从小到大选择（编号不会重复）
输入：
第一行：服务器数量M
接下来M行为M台服务器属性的数组
下一行为分配要求：最大分配数量N，分配策略strategy，cupCount，memSize，cpuArch，supportNP
其中：
1<=M<=1000
1<=N<=1000
strategy：1表示策略1,2表示策略2
1<=cpuCount<=100
10<=memSize<=1000
0<=cpuArch<=8，另外，cpuArch使用9表示所有服务器架构都满足分配要求
0<=supportNP<=1，另外，为2时表示无论是否支持NP加速都满足分配要求
输出
先输出实际分配数量，后按照分配的服务器编号从小到大依次输出，以空格分开
样例1
输入 4 0,2,200,0,1 1,3,400,0,1 2,3,400,1,0 3,3,300,0,1 3 1 3 200 0 1 输出 2 1 3 解释：只有1和3满足要求，要求分配2台服务器，所以结果为2 1 3样例2
输入 6 0,2,200,0,1 1,4,330,2,1 2,3,400,3,1 3,3,310,1,1 4,3,320,8,1 5,3,330,0,1 3 2 3 300 9 2 （这里注意一下输入的格式，最后一行是空格分开） 输出 3 3 4 5 解释：编号1~5都满足分配要求，按策略2分配即内存优先，内存>=300并且最接近300的服务器编号是3 4 1 5 2。 其中1和5内存相同，然后会比较CPU，即CPU>=3且最接近的，所以5优先于1.因此最后分配的三台服务器是3 4 5。 输出时先输出数量3，再按编号排序输出3 4 5思路：一个模拟，自定义排序即可
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int M = Integer.parseInt(scanner.nextLine());
int[][] service = new int[M][5];
for (int i = 0; i < M; i++) {
String[] str = scanner.nextLine().split(",");
for (int j = 0; j < 5; j++) {
service[i][j] = Integer.parseInt(str[j]);
}
}
int N = scanner.nextInt();
int strategy = scanner.nextInt();
int cpuCount = scanner.nextInt();
int memSize = scanner.nextInt();
int cpuArch = scanner.nextInt();
int supportNP = scanner.nextInt();
PriorityQueue<int[]> queue = null;
if (strategy == 1) {
queue = new PriorityQueue<>((o1, o2) -> {
if (o1[1] != o2[1]) {
return o1[1] - o2[1];
} else {
if (o1[2] != o2[2]) {
return o1[2] - o2[2];
} else {
return o1[0] - o2[0];
}
}
});
}
if (strategy == 2) {
queue = new PriorityQueue<>((o1, o2) -> {
if (o1[2] != o2[2]) {
return o1[2] - o2[2];
} else {
if (o1[1] != o2[1]) {
return o1[1] - o2[1];
} else {
return o1[0] - o2[0];
}
}
});
}
for (int i = 0; i < M; i++) {
if (service[i][1] >= cpuCount && service[i][2] >= memSize
&& (service[i][3] == cpuArch || cpuArch == 9)
&& (service[i][4] == supportNP || supportNP == 2)) {
queue.add(service[i]);
}
}
int resCount = Math.min(queue.size(), N);
int[] res = new int[resCount];
for (int i = 0; i < resCount; i++) {
res[i] = queue.poll()[0];
}
Arrays.sort(res);
System.out.print(resCount);
for (int i = 0; i < resCount; i++) {
System.out.print(" " + res[i]);
}
}
} 第二题
工单调度策略
当小区通信设备上报警时，系统会自动生成待处理的工单，工单调度系统需要根据不同的策略，调度外线工程师（FME）上站去修复工单对应的问题。根据与运营商签订的合同，不同严重程度的工单被处理并修复的时长要求不同，这个要求被修复的时长我们称之为SLA时间。假设华为与运营商A签订了运维合同，部署了一套调度系统，只有1个外线工程师（FME），每个工单根据问题严重程度会给一个评分，在SLA时间内完成修复的工单，华为员工获得工单对应的积分，超过SLA完成的工单不获得积分，但必须完成该工单，运营商最终会根据积分付款。
请设计一种调度策略，根据现状得到调度结果完成所有工单，让这个外线工程师处理的工单处理的工单获得的总积分最多。
假设从某个调度时刻开始，当前工单数量N，不会产生新的工单，每个工单处理修复耗时为1小时。请设计你的调度策略，完成业务目标。不考虑外线工程师在小区之间行驶的耗时。
输入
第一行为一个整数N，表示工单的数量。
接下来N行，每行包括两个整数，第一个整数表示工单的SLA时间（小时），第二个数表示工单的积分。
输出
输入一个证书表示可以获得的最大积分
样例1
假设有7个工单的SLA时间（小时）和积分如下：
| 工单编号 | SLA 积分 | 积分 |
| 1 | 1 | 6 |
| 2 | 1 | 7 |
| 3 | 3 | 2 |
| 4 | 3 | 1 |
| 5 | 2 | 4 |
| 6 | 2 | 5 |
| 7 | 6 | 1 |
最多可获得15积分，其中一个调度结果完成工单顺序为2，6，3，1，7，5，4（可能还有其他顺序）
输入 7 1 6 1 7 3 2 3 1 2 4 2 5 6 1 输出 15 提示： 工单数量N ≤106 SLA时间 ≤ 7×105 答案的最大积分不会超过2147483647这道题如果按贪心的思想
一：优先选择积分大的，积分相同，等待时间选小的。可以通过题目样例。但是**不对**，因为存在下面这种情况(借鉴了评论区)
3
1 5
2 9
3 10
最大应该是9+5+10，却输出19
二：所以优先先对等待时间从小到大进行排序，如果遇到积分相同的情况，则按照积分降序，则可以避免这种情况。但是还是错的，比如下面样例
3
1 2
2 8
2 8
最大应该是16，却输出10
三：那么如果同时进行上面的两种排序，选最大值呢，还是错的，比如下面的样例
4
1 2
2 7
2 8
3 8
最大应该是7+8+8=23，但是
优先时间输出的是2+8+8=18
优先积分输出的是8+8=16
都小于23
正确思想：贪心+优先级队列
贪心最优概念：我们必须保证处理工单的一个顺序是优先选择时间最短最紧急的，如果时间相同，那么选积分大的。这一定可以得到最优解。选择时间短的，我们任然有机会处理后面的积分大的值。而如果先处理积分大的，那么时间短的一定会漏掉。
队列更新：那么问题来了，怎么避免上面讨论的第二种情况呢，即后面时间长的积分更大的值。我们可以定义一个优先级队列，保存我们要处理的工单。优先级队列定义为按照积分的大小从小到大排序。
添加进队列的前提是输入数组已经进行贪心排序之后。然后，从第一个任务开始遍历，如果满足时间要求，加入队列。如果不满足，我们可以与当前的队头的积分进行比较，如果现在的更大，我们可以弹出队首，用当前的元素替换，因为队头元素是积分最小的。
最后遍历完毕后，队列中保存的一定是得到最大积分值的一个工单集合
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int N = scanner.nextInt();
if(N==0){
System.out.println(0);
return;
}
//tasks数组保存输入,tasks[i][0]代表工单等待时长，tasks[i][1]代表对应分数
int[][]tasks=new int[N][2];
for (int i = 0; i < N; i++) {
for (int j = 0; j < 2; j++) {
tasks[i][j] = scanner.nextInt();
}
}
//我们首先应该选择等待时间小的，时间从0开始一个个判断，如果相等在选择积分大的。这样得到的肯定是最优的
Arrays.sort(tasks, (a, b) -> a[0]==b[0]?b[1]-a[1]:a[0]-b[0]);
//这里需要按照积分从小到大排序
Queue<int[]> q = new PriorityQueue<>((a, b) -> a[1] - b[1]);
//当前处理工单耗时
int cur_time = 0;
//积分总和
int ans=0;
for (int i=0;i<tasks.length;i++) {
int time = tasks[i][0], sorce = tasks[i][1];
if(time>cur_time){
//增加时长（可以看到，队列的长度就是当前时长。因为每个工单都是耗时一小时）
cur_time++;
q.offer(tasks[i]);
}else if(!q.isEmpty() && q.peek()[1] <sorce) {
//队首工单我们撤销处理，有可以处理的积分更大的
q.poll();
q.offer(tasks[i]);
}
}
//此时，队列中保存的就是满足条件的工单
while (!q.isEmpty()){
ans+=q.poll()[1];
}
System.out.println(ans);
}
} 第三题
分发糖果
老师给两个同学分糖果，每袋糖果中的数量不完全一样。一袋糖果只能分给一个人，并且一次性全分完必须。两个人分到的糖果数必须相同。返回两个人分到的糖果数，无法平均分配，返回-1。输入
第一行输入糖果袋数，范围是[1,100]
第二行是一个数组，每袋糖果数量，范围[1,100]
输出
第一行为每人分到的糖果总数，不能平均分配，输出-1
第二行，第三行为两个同学分配到的每袋糖果具体的糖果数，顺序不限
存在多种分配方式时，输出任意一种可行的方法即可
样例1
输入 1 100 输出 -1 解释：无法平均分配样例2
输入 5 7 4 5 3 3 输出 11 7 4 5 3 3 解释：无法平均分配思路：这道题可以转化为一个0-1背包问题（笔试时，没弄出来，直接输出-1过了百分之五）
参考题目[剑指 Offer II 101. 分割等和子集]
不同的就是需要记录一下选择路径（下面是一个评论区一个大佬的题解，比我的简洁）
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int[] data = new int[n];
int sum = 0;
for (int i = 0; i < n; i++) {
data[i] = scanner.nextInt();
sum += data[i];
}
if (sum % 2 == 1 || n == 1) {
System.out.println(-1);
return;
}
int target = sum / 2;
// 转换为0-1背包问题
// 创建二维状态数组，行：糖果索引，列：容量，dp[i][j] 表示从数组的 前i袋糖果
// 范围内选取若干个正整数（可以是 0 个），是否存在一种选取方案使得被选取的正整数的和等于 j。初始时，dp 中的全部元素都是false。
boolean[][] dp = new boolean[n + 1][target + 1];
// 如果不选取任何正整数，则被选取的正整数等于 0。因此对于所有 0≤i<=n，都有 dp[i][0]=true
for (int i = 0; i <= n; i++) {
dp[i][0] = true;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= target; j++) {
if (j - data[i - 1] < 0) {
dp[i][j] = dp[i - 1][j];
} else {
dp[i][j] = dp[i - 1][j] | dp[i - 1][j - data[i - 1]];
}
}
}
//通过dp可以判断选择前几袋糖果是否可以找到和为target
// 并且我们可以通过下面的判断直接得到选了哪些糖果（结果可能有多种，这是按遍历顺序得到的)
List<Integer>resLi=new ArrayList<>();
while (target>0){
for (int i = 0; i <= n; i++) {
//找到第一个满足target的糖果，肯定选择了此袋糖果
if(dp[i][target]){
resLi.add(data[i-1]);
//更新target
target=target-data[i-1];
//下次遍历直接到前n-1袋即可
n=i-1;
break;
}
}
}
Map<Integer,Integer>map=new HashMap<>();
for (int datum : data) {
map.put(datum, map.getOrDefault(datum, 0) + 1);
}
//下面处理输出
System.out.println(sum/2);
for (int i=0;i<resLi.size();i++) {
if(i==0){
System.out.print(resLi.get(i));
map.put(data[i],map.get(data[i])-1);
}else {
System.out.print(" "+resLi.get(i));
map.put(data[i],map.get(data[i])-1);
}
}
List<Integer>resHan=new ArrayList<>();
for (int datum : data) {
if (map.get(datum) > 0) {
resHan.add(datum);
map.put(datum, map.get(datum) - 1);
}
}
System.out.println();
for (int i = 0; i <resHan.size() ; i++) {
if(i==0){
System.out.print(resHan.get(i));
}else {
System.out.print(" "+resHan.get(i));
}
}
}
} 
查看5道真题和解析
