【华为OD题库-102】排队游戏-java

题目

新来的老师给班里的同学排一个队。每个学生有一个能力值。一些学生是刺头，不会听老师的话，自己选位置，非刺头同学在剩下的位置按照能力值从小到大排。对于非刺头同学，如果发现他前面有能力值比自己高的同学，他不满程度就增加，增加的数量等于前面能力值比他大的同学的个数。刺头不会产生不满。如果整个班级累计的不满程度超过k，那么老师就没有办法教这个班级了.
输入描述
输入有三行:
第一行为n,m,k,空格隔开，分别表示班级总人数，刺头人数，最大不满程度k.
第二行为刺头所在位置(从0开始，即排队数组的下标，比如1代表队伍中第2个同学是刺头)，位置的数组也是排序的.
第三行有n个数，空格隔开，表示老师排好的队中每人人的能力值，其中非刺头同学一定按照能力值从小到大排好序的
输出描述
0表示老师可以继续教这个班级
1表示老师无法继续教这个班级
说明:
n范围是[1,10000]
m范围是[1,n]
k范围是[1,1000000000]
每位同学的能力值范围是[1000,100000]
示例1:
输入
4 2 3
0 1
1810 1809 1801 1802
输出
1
说明
刺头在0,1位置，2号同学不满程度2(前面两人刺头能力值都比他大)，3号同学不满程度2，总不满程度4，大于3。输出不能教这班(1).
示例2:
输入
4 2 4
0 1
1810 1809 1801 1802
输出:
0
说明:
同前，4不大于4，输出能教这个班(0)

思路

根据题意，知道一个能力值nums，并且知道其中刺头所在的索引。

1. 直接遍历nums，当该位置为刺头时，将刺头数据加入一种数据结构存储起来，比如list
2. 如果该位置不为刺头，此时查找list中比当前值还大的数据的个数，此个数就为当前学生的不满意程度
3. 最后计算累计的不满意程度是否超过阈值k即可

关键在于第二步，方案有二：

1. 直接写个单独的for循环查找，list中比给定值还大的元素个数
2. 不使用list存刺头能力值数据，而是用TreeSet存，利用treeSet.tailSet()方法可以获取比指定元素大的元素个数，此时需要注意，刺头的能力值可能重复，因此treeSet中不能直接存放能力值，而是将能力值和索引一起存储，这样就不会有重复数据了

题解

package hwod;

import java.util.*;

public class QueueGame {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int k = sc.nextInt();
        int[] ctIdxs = new int[m];
        for (int i = 0; i < m; i++) {
            ctIdxs[i] = sc.nextInt();
        }
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = sc.nextInt();
        }
        System.out.println(queueGame2(nums, ctIdxs, k));
    }
    //方案一，循环查找

    /**
     * @param nums   班级能力值数组
     * @param ctIdxs 刺头所在的索引
     * @param k      最大不满程度
     * @return
     */
    private static int queueGame(int[] nums, int[] ctIdxs, int k) {
        int notSatisfied = 0;//不满意程度
        int j = 0;
        List<Integer> list = new ArrayList<>();//存放刺头
        for (int i = 0; i < nums.length; i++) {
            if (j < ctIdxs.length && i == ctIdxs[j]) {
                list.add(nums[i]);
                j++;
            } else {
                //非刺头，计算前面必自己能力值大的个数，list中比自己还要大的个数
                notSatisfied += getBiggerThanNow(list, nums[i]);

            }
        }
        if (notSatisfied > k) return 1;
        return 0;
    }

    private static int getBiggerThanNow(List<Integer> list, int num) {
        int res = 0;
        for (int i = 0; i < list.size(); i++) {
            if (list.get(i) > num) res++;
        }
        return res;
    }

    //方案二：利用TreeSet存数据
    private static int queueGame2(int[] nums, int[] ctIdxs, int k) {
        int notSatisfied = 0;//不满意程度
        int j = 0;
        TreeSet<int[]> set = new TreeSet<>((o1, o2) -> {
            if (o1[1] != o2[1]) return o1[1] - o2[1];
            return o1[0] - o2[0];
        });//存放刺头,按照能力从小到大排，能力相同则根据索引从先到后排
        for (int i = 0; i < nums.length; i++) {
            if (j < ctIdxs.length && i == ctIdxs[j]) {
                set.add(new int[]{i, nums[i]});
                j++;
            } else {
                //非刺头，计算前面必自己能力值大的个数，set中比自己还要大的个数
                notSatisfied += set.tailSet(new int[]{i, nums[i]}).size();

            }
        }
        if (notSatisfied > k) return 1;
        return 0;
    }
}

推荐

如果你对本系列的其他题目感兴趣，可以参考华为OD机试真题及题解（JAVA），查看当前专栏更新的所有题目。