新来的老师给班里的同学排一个队。每个学生有一个能力值。一些学生是刺头，不会听老师的话，自己选位置，非刺头同学在剩下的位置按照能力值从小到大排。对于非刺头同学，如果发现他前面有能力值比自己高的同学，他不满程度就增加，增加的数量等于前面能力值比他大的同学的个数。刺头不会产生不满。如果整个班级累计的不满程度超过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，并且知道其中刺头所在的索引。
- 直接遍历nums，当该位置为刺头时，将刺头数据加入一种数据结构存储起来，比如list
- 如果该位置不为刺头，此时查找list中比当前值还大的数据的个数，此个数就为当前学生的不满意程度
- 最后计算累计的不满意程度是否超过阈值k即可
关键在于第二步，方案有二：
- 直接写个单独的for循环查找，list中比给定值还大的元素个数
- 不使用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），查看当前专栏更新的所有题目。