蓝桥杯2022年省赛JAVA B组第四题

题目

小蓝老师教的编程课有N名学生，编号依次是 1…N。

第i号学生这学期刷题的数量是Ai，对于每一名学生，

请你计算他至少还要再刷多少道题，才能使得全班刷题比他多的学生数不超过刷题比他少的学生数。

【输入格式】

第一行包含一个正整数N
第二行包含N个整数：A₁-A_i

【输出格式】

输出N个整数，依次表示第 1…N号学生分别至少还要再刷多少道题。

【样例输入】

5
12 10 15 20 6

【样例输出】

0 3 0 0 7

思路分析

这道题容易陷入的一个误区是，误以为是每一个学生的变化都会引起别人的变化，实际上题目说明的是对每一个学生来说，也就是他只知道自己的变化，并不知道别人的变化。这个误区可以说是致命的

录入数据

这个很简单

        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = scanner.nextInt();
        }

复制数组并排序

为了数据的安全与方便，把数据拷贝出一份使用最为安全。

数组拷贝不需要自己单独写方法，JAVA就提供了现成的方法

//用到Arrays类的copyOfRange(int[] original, int from, int to)
//需要特别注意的是范围[from,to)区间是左闭右开

int[] temp = new int[arr.length];
System.arraycopy(arr, 0, temp, 0, arr.length);

数组的排序也不需要自己去写，自带的排序是快排，也很快速了

Arrays.sort(copyarr);

具体情况的分析考虑

先考虑样例

12 10 15 20 6

排序之后为 6 10 12 15 20

我们的目标为比自己多的人数不超过比自己少的人数

在排序之后我们会直接发现比刷题数中间值还多的人本身就符合这个要求

比如15，比15多的人有1个，比15少的人有3个，1不超过3，符合

对于这个样例的中间值12，比12多的有2个，比12少的有2个，2不超过2，也符合

那么我们就暂时可以说处于中间值或者比中间值大的就符合这个条件。

那么对于比中间值少的人，10，比10大的有3个，比10少的有1个，这就不符合了。

如何将他变为符合的呢？

将他变大到中间值或者比中间值大，根据样例输出，将10＋3，变为13 也就是比中间值稍大。那么我们考虑一下变为中间值可不可以呢？

假如变为12，数据将会变为 6 12 12 15 20，比12大的有2个，比12小的有1个，不符合

那么我们就可以说，比中间值大的一定符合，中间值不一定符合。由于我们所需要的是至少。所以我们需要去考虑一下各种情况

中间值是否符合

那么就需要去考虑中间值何时就不符合，有三个样例

6 10 10 15 20中间值为10，中间值不符合

6 9 10 10 15中间值为10，中间值符合

6 9 10 12 15中间值为10，中间值符合

那么就可以发现比中间值大的数多于比中间值小的数那么中间值就不符合

那么就需要去考虑一下将比中间值小的数是变为中间值还是变为中间值+1

小于中间值的如何变化

6 10 10 15 20 大于的中值多于小于中值的，需要变为中间值加一

6 9 10 10 15 大于中间值少于小于的，变为中间值即可

6 9 10 12 15 大于中间值等于小于的，需要变为中间值加一

那么就很清晰了，需要先判断比中值大和小的个数

记录more和less

more代表比中值大的

less代表比中值小的

mid代表中值的下标

        int len = temp.length-1;//为的是计算下标的中值
        int mid = (len & 1) == 0 ? len >> 1 : (len >> 1) + 1;
        int more = 0;
        int less = 0;
        for (int i = 0; i < temp.length; i++) {
            if (temp[i]<temp[mid]){
                less++;
            } else if (temp[i] > temp[mid]) {
                more++;
            }
        }

根据分类确定几个变量

有两个变量需要去确定

一个是中间值是否需要加一

一个是需要变为中间值还是中间值加一

        int flag = 0;
        int midFlag = 0;
        if (more>=less){
            flag = 1;
        }
        if (more > less) {
            midFlag = 1;
        }

遍历去生成答案

对于大于中值的

不予理会，将它设为0

对于等于中值的，将它设为midflag

对于小于中值的，将它设为mid+flag - 原值

        for (int i = 0; i < arr.length; i++) {
            if (arr[i] < temp[mid]) {
                arr[i] = temp[mid] + flag - arr[i];
            } else if (arr[i] == temp[mid] && midFlag == 1) {
                arr[i] = midFlag;
            } else {
                arr[i] = 0;
            }
        }

那么这就结束了，如果需要进行一下判题可以去AcWing去检测一下

完整代码

package blue.T2022_4;

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    /*
    小蓝老师教的编程课有N名学生，编号依次是 1…N。
    第i号学生这学期刷题的数量是Ai
    对于每一名学生，请你计算他至少还要再刷多少道题，才能使得全班刷题比他多的学生数不超过刷题比他少的学生数。
     */
    /*
    值得注意的是，这个只针对单个人的变化，别人的变化不对本人有效
     */
    public static void main(String[] args) {
        //首先是接受数据
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = scanner.nextInt();
        }
        int[] temp = new int[arr.length];
        System.arraycopy(arr, 0, temp, 0, arr.length);
//        5
//        12 10 15 20 6
        //核心思路是判断比自己刷题多的人数和比自己刷题少的人数
        //首先就是先让数组有序
        Arrays.sort(temp);
        int len = temp.length-1;
        int mid = (len & 1) == 0 ? len >> 1: (len >> 1) + 1;
        int more = 0;
        int less = 0;
        for (int i = 0; i < temp.length; i++) {
            if (temp[i] < temp[mid]) {
                less++;
            } else if (temp[i] > temp[mid]) {
                more++;
            }
        }
        int flag = 0;
        int midFlag = 0;
        if (more >= less) {
            flag = 1;
        }
        if (more > less) {
            midFlag = 1;
        }
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] < temp[mid]) {
                arr[i] = temp[mid] + flag - arr[i];
            } else if (arr[i] == temp[mid] && midFlag == 1) {
                arr[i] = midFlag;
            } else {
                arr[i] = 0;
            }
        }
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");//不换行
        }
    }
}

题目