(B卷,200分)- 排队游戏（Java & JS & Python & C）

题目描述

新来的老师给班里的同学排一个队。

每个学生有一个影力值。

一些学生是刺头，不会听老师的话，自己选位置，非刺头同学在剩下的位置按照能力值从小到大排。

对于非刺头同学，如果发现他前面有能力值比自己高的同学，他不满程度就增加，增加的数量等于前面能力值比他大的同学的个数。

刺头不会产生不满。

如果整个班级累计的不满程度超过k，那么老师就没有办法教这个班级了。

输入描述

输入有三行：

第一行为n,m,k,空格隔开，分别表示班级总人数，刺头人数，最大不满程度k。

第二行为刺头所在位置(从0开始，即排队数组的下标，比如1代表队伍中第2个同学是刺头)，位置的数组也是排序的。

第三行有n个数，空格隔开，表示老师排好的队中每个人的能力值，其中非刺头同学一定按照能力值从小到大排好序的。

输出描述

0 表示老师可以继续教这个班级

1 表示老师无法继续教这个班级

备注

• n 范围是[1,100000]
• m 范围是 [1,n]
• k 范国是[1,1000000000]
• 每位同学的能力值范围是[1000,100000]

用例

题目解析

本题可以使用二分查找解题。

题目说：

非刺头同学在剩下的位置按照能力值从小到大排。

因此，每个非刺头学生，其实只需要关注他前面的刺头学生即可，因为他前面的非刺头学生的能力值一定不大于他。

我们可以定义一个集合 pricks 来记录刺头学生的能力值。

因此，我们遍历所有学生能力值时：

• 如果当前位置是刺头学生（根据第二行输入的刺头学生位置判断），那么就将当前学生能力值ability加入到pricks中，这里我们需要保证有序插入到 pricks 中。
• 如果当前位置是非刺头学生，那么我们需要找到当前学生能力值ability在pricks中的排名rank（其实也是有序插入位置），找到排名后，范围[rank, pricks.length – 1]内刺头学生都是能力比当前学生高的

按此逻辑，我们只要收集非刺头学生 前面 能力比自己高的 非刺头学生个数，如果最后总个数 > k，则老师无法教此班级，否则就可以。

上面逻辑中，我们有两个动作：

• 向 pricks 中有序插入 ability（注意，本题pricks从空开始有序插入，因此可以保证一直有序）
• 在 pricks 中找到 ability 的排名 （最后一个有序插入位置）

而这可以基于二分查找实现。

但是，pricks 中是有可能存在多个相同能力值的，对于这种情况，我们应该将ability插入到pricks中和ability相同的最后一个能力值的后面，这样才能保证 ability 被插入后，其后面值都比 ability 高。

关于在pricks中寻找和ability相同的最后一个能力值的位置，具体实现可以参考下面博客中searchLast方法：

JS算法源码

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void (async function () {
  // 班级总人数, 刺头人数, 最大不满程度
  const [n, m, k] = (await readline()).split(" ").map(Number);
  // 刺头所在位置
  const pricks_idx = new Set((await readline()).split(" ").map(Number));
  // 所有学生的能力值
  const all = (await readline()).split(" ").map(Number);

  // 总不满意程度
  let unHappy = 0;

  // 记录所有刺头的能力
  const pricks = [];
  for (let i = 0; i < n; i++) {
    // 当前学生能力
    const ablity = all[i];

    // 当前学生能力在刺头中的排名, 这里使用二分查找pricks中最后一个等于ability的位置，如果pricks中没有等于ability的值，则返回第一个大于ability的位置
    let rank = searchLast(pricks, ablity);

    if (rank < 0) {
      rank = -rank - 1;
    } else {
      rank += 1;
    }

    if (pricks_idx.has(i)) {
      // 如果当前学生是刺头，那么就（有序）插入到刺头学生中
      pricks.splice(rank, 0, ablity);
    } else {
      // 如果当前学生是非刺头，那么 [rank ~ pricks.size() - 1] 范围的所有刺头学生都是能力值比当前学生高的
      unHappy += pricks.length - rank;
    }
  }

  console.log(unHappy > k ? 1 : 0);
})();

function searchLast(arr, target) {
  let low = 0;
  let high = arr.length - 1;

  while (low <= high) {
    const mid = (low + high) >> 1;
    const midVal = arr[mid];

    if (midVal > target) {
      high = mid - 1;
    } else if (midVal < target) {
      low = mid + 1;
    } else {
      // 向右延伸判断，mid是否为target数域的右边界，即最后一次出现的位置
      if (mid == arr.length - 1 || arr[mid] != arr[mid + 1]) {
        return mid;
      } else {
        low = mid + 1;
      }
    }
  }

  return -low - 1; // 找不到则返回插入位置
}

Java算法源码

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Scanner;

public class Main {

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    // 班级总人数
    int n = sc.nextInt();
    // 刺头人数
    int m = sc.nextInt();
    // 最大不满程度
    int k = sc.nextInt();

    // 刺头所在位置
    HashSet<Integer> pricks_idx = new HashSet<>();
    for (int i = 0; i < m; i++) {
      pricks_idx.add(sc.nextInt());
    }

    // 总不满意程度
    int unHappy = 0;

    // 记录所有刺头的能力
    ArrayList<Integer> pricks = new ArrayList<>();
    for (int i = 0; i < n; i++) {
      // 当前学生能力
      int ability = sc.nextInt();

      // 当前学生能力在刺头中的排名, 这里使用二分查找pricks中最后一个等于ability的位置，如果pricks中没有等于ability的值，则返回第一个大于ability的位置
      int rank = searchLast(pricks, ability);

      if (rank < 0) {
        rank = -rank - 1;
      } else {
        rank += 1;
      }

      if (pricks_idx.contains(i)) {
        // 如果当前学生是刺头，那么就（有序）插入到刺头学生中
        pricks.add(rank, ability);
      } else {
        // 如果当前学生是非刺头，那么 [rank ~ pricks.size() - 1] 范围的所有刺头学生都是能力值比当前学生高的
        unHappy += pricks.size() - rank;
      }
    }

    System.out.println(unHappy > k ? 1 : 0);
  }

  public static int searchLast(ArrayList<Integer> list, int target) {
    int low = 0;
    int high = list.size() - 1;

    while (low <= high) {
      int mid = (low + high) >> 1;
      int midVal = list.get(mid);

      if (midVal > target) {
        high = mid - 1;
      } else if (midVal < target) {
        low = mid + 1;
      } else {
        // 向右延伸判断，mid是否为target数域的右边界，即最后一次出现的位置
        if (mid == list.size() - 1 || list.get(mid) - list.get(mid + 1) != 0) {
          return mid;
        } else {
          low = mid + 1;
        }
      }
    }

    return -low - 1; // 找不到则返回插入位置
  }
}

Python算法源码

n, m, k = map(int, input().split())  # 班级总人数, 刺头人数, 最大不满程度
pricks_idx = set(map(int, input().split()))  # 刺头所在位置
all_ability = list(map(int, input().split()))  # 所有学生能力


def searchLast(arr, target):
    low = 0
    high = len(arr) - 1

    while low <= high:
        mid = (low + high) >> 1
        midVal = arr[mid]

        if midVal > target:
            high = mid - 1
        elif midVal < target:
            low = mid + 1
        else:
            if mid == len(arr) - 1 or arr[mid] != arr[mid + 1]:
                return mid
            else:
                low = mid + 1

    return -low - 1


def getResult():
    # 总不满意程度
    unHappy = 0

    # 记录所有刺头的能力
    pricks = []
    for i in range(n):
        # 当前学生能力
        ability = all_ability[i]

        # 当前学生能力在刺头中的排名, 这里使用二分查找pricks中最后一个等于ability的位置，如果pricks中没有等于ability的值，则返回第一个大于ability的位置
        rank = searchLast(pricks, ability)

        if rank < 0:
            rank = -rank - 1
        else:
            rank += 1

        if i in pricks_idx:
            # 如果当前学生是刺头，那么就（有序）插入到刺头学生中
            pricks.insert(rank, ability)
        else:
            # 如果当前学生是非刺头，那么 [rank ~ pricks.size() - 1] 范围的所有刺头学生都是能力值比当前学生高的
            unHappy += len(pricks) - rank

    return 1 if unHappy > k else 0


print(getResult())

C算法源码

#include <stdio.h>

#define MAX_SIZE 100000

typedef int bool;
#define TRUE 1
#define FALSE 0

int searchLast(int* arr, int arr_size, int target);
void insert(int* arr, int* arr_size, int insert_idx, int insert_val);

int main()
{
// 班级总人数, 刺头人数, 最大不满程度
int n, m, k;
scanf("%d %d %d", &n, &m, &k);

// 刺头所在位置
bool isPrick[MAX_SIZE] = {FALSE};
for(int i=0; i<m; i++) {
int idx;
scanf("%d", &idx);
isPrick[idx] = TRUE;
}

// 总不满意程度
int unHappy = 0;

// 记录所有刺头的能力
int pricks[MAX_SIZE];
int pricks_size = 0;

for(int i=0; i<n; i++) {
// 当前学生能力
int ability;
scanf("%d", &ability);

// 当前学生能力在刺头中的排名, 这里使用二分查找pricks中最后一个等于ability的位置，如果pricks中没有等于ability的值，则返回第一个大于ability的位置
int rank = searchLast(pricks, pricks_size, ability);

if(rank < 0) {
rank = -rank - 1;
} else {
rank += 1;
}

if(isPrick[i]) {
// 如果当前学生是刺头，那么就（有序）插入到刺头学生中
insert(pricks, &pricks_size, rank, ability);
} else {
// 如果当前学生是非刺头，那么 [rank ~ pricks.size() - 1] 范围的所有刺头学生都是能力值比当前学生高的
unHappy += pricks_size - rank;
}
}

printf("%dn", unHappy > k ? 1 : 0);

return 0;
}

int searchLast(int* arr, int arr_size, int target)
{
int low = 0;
int high = arr_size- 1;

while(low <= high) {
int mid = (low + high) >> 1;
int midVal = arr[mid];

if(midVal > target)
{
high = mid - 1;
} 
else if(midVal < target)
{
low = mid + 1;
}
else
{
// 向右延伸判断，mid是否为target数域的右边界，即最后一次出现的位置
if(mid == arr_size - 1 || arr[mid] - arr[mid+1] != 0)
{
return mid;
}
else
{
low = mid + 1;
}
}
}

return -low - 1; // 找不到则返回插入位置
}

void insert(int* arr, int* arr_size, int insert_idx, int insert_val)
{
for(int i = *arr_size - 1; i >= insert_idx; i--) {
arr[i+1] = arr[i];
}

arr[insert_idx] = insert_val;

(*arr_size)++;
}