试题 D: 最少刷题数

时间限制: 1.0s 内存限制: 512.0MB 本题总分：10 分
【问题描述】
小蓝老师教的编程课有 N 名学生，编号依次是 1 . . . N。第 i 号学生这学期
刷题的数量是 Ai。
对于每一名学生，请你计算他至少还要再刷多少道题，才能使得全班刷题
比他多的学生数不超过刷题比他少的学生数。
【输入格式】
第一行包含一个正整数 N。
第二行包含 N 个整数：A1, A2, A3, . . . , AN.
【输出格式】
输出 N 个整数，依次表示第 1 . . . N 号学生分别至少还要再刷多少道题。
【样例输入】
5
12 10 15 20 6
【样例输出】
0 3 0 0 7
【评测用例规模与约定】
对于 30% 的数据，1 ≤ N ≤ 1000, 0 ≤ Ai ≤ 1000.
对于 100% 的数据，1 ≤ N ≤ 100000, 0 ≤ Ai ≤ 100000.

思路分析：

//题意关键：使得全班刷题比他多的学生数 不超过 刷题比他少的学生数。
//思路分析
//分析样例 找到中间值12 比12大的有两个 比12小的有两个
//10比12小 想要满足题意 就要+3 变成13
//6比12小 想要满足题意  就要变成13 就是要加7(13-6=7)
//所以关键是要找到 中间值！
//第1步 找中间值.
//API查看Arrays类(此类包含用来操作数组（比如排序和搜索）的各种方法)
//  1.1将数组copy(拷贝)一个一模一样的新数组copyarr
//     用到copyOfRange(int[] original, int from, int to)
//     其方法是 将指定数组的指定范围复制到一个新数组。

// 然后对copyarr排序  Arrays.sort(copyarr);
//  1.2找中间值median = copyarr[arr.length / 2]
//第2步 循环arr 让arr[i]与median比
//  如果arr[i] < median 就arr[i]=median+1-arr[i];
//  如果arr[i] >= median 就arr[i] = 0;
看到这里建议把以上思路完成，再继续看以下思路

//多测试几组数据 发现一个问题！
//  当arr元素为: 3 4 6 10 10 14
//  中间值=10
//  题意：使得全班刷题比他多的学生数 不超过 刷题比他少的学生数。
//  对于3来说变成10就满足题意 不用变成11
//  对于4来说变成10就满足题意 不用变成11
//  这种情况 是直接变成中间值 而不是中间值+1

//第3步 改代码!             -----这是这道题能不能拿到 近一半分数 的关键
//  arr中 (大于中间值的数量)小于(小于中间值的数量）变成中间值
//      例如： 3  4  6  10  10  14  变成10
//  arr中 (大于中间值的数量)等于(小于中间值的数量）变成中间值+1
//      例如： 6  10 12 15  20      变成13
//  arr中 (大于中间值的数量)大于(小于中间值的数量）变成中间值+1
//      例如： 3  10 10 10  12  14  变成11
//关键之处判断(大于中间值的数量)与(小于中间值的数量）的大小关系

看到这里建议把以上思路完成，再继续看以下思路

            //看第4步之前 把前3步先理解了
// 第4步 增加对中间值的判断     -----这是这道题能不能拿到 满分 的关键
//第4步 接着跟这是否要 “加1” 这个思路 对中间值 进行判断  ！！！
            // 看下边三组数据  中间值是10
            //再读一下题意：使得全班刷题比他多的学生数 不超过 刷题比他少的学生数
//3  10   10    12  14  中间值 10要变大  就是10也要变成 中间值+1 ！！！
//3  4    10    10  14  中间值 10不用变
//3  4    10    12  14  中间值 10不用变

package lanqiao13;

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

/**
 * 杨亚磊
 */

public class D {

    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 < n; i++) {
            arr[i] = scanner.nextInt();
        }
        //记录程序运行起始时间
        long timeMillis = System.currentTimeMillis();

        //找中间值
        //1.1将数组copy(拷贝)一个一模一样的新数组
        //用到Arrays类的copyOfRange(int[] original, int from, int to)
        //需要特别注意的是范围[from,to)区间是左闭右开
        int[] copyarr = Arrays.copyOfRange(arr, 0, arr.length);
        System.out.println("拷贝的新数组" + Arrays.toString(copyarr));
        Arrays.sort(copyarr);
        System.out.println("拷贝的新数组排序后" + Arrays.toString(copyarr));
        System.out.println("中间值=" + copyarr[arr.length / 2]);
        int median = copyarr[arr.length / 2];

//        //第2步 循环arr与median比
//        for (int i = 0; i < arr.length; i++) {
//            if (arr[i] < median) {
//                arr[i] = median+1-arr[i];
//            } else arr[i] = 0;
//        }


        //第3步 改代码!
//        int flag = 0;//建立一个是否+1的标志  默认不加
//        int less = 0;//记录小于中间值的数量
//        int more = 0;//记录大于中间值的数量
//        for (int i = 0; i < arr.length; i++) {
//            if (arr[i] > median) more++;
//            if (arr[i] < median) less++;
//        }
//    //  arr中 (大于中间值的数量)小于(小于中间值的数量）变成中间值
//    //      例如： 3  4  6  10  10  14  变成10
//    //  arr中 (大于中间值的数量)等于(小于中间值的数量）变成中间值+1
//    //      例如： 6  10 12 15  20      变成13
//    //  arr中 (大于中间值的数量)大于(小于中间值的数量）变成中间值+1
//    //      例如： 3  10 10 10  12  14  变成11
//        if (more >= less) flag = 1;
//
//        //第3步 改变arr
//        //循环arr与median比
//        //使得全班刷题比他多的学生数 不超过 刷题比他少的学生数。
//        for (int i = 0; i < arr.length; i++) {
//            //3  10   10    12  14  中间值 10要变大
//            //3  4    10    10  14  中间值 10不用变
//            if (arr[i] < median) {
//                arr[i] = median + flag - arr[i];
//            } else {
//                //这里等于中间值的 和 大于中间值的 arr[i] 都为 0是不对的 第四步有分析
//                arr[i] = 0;
//            }
//        }




        //3  10   10    12  14  中间值 10要变大
        //3  4    10    10  14  中间值 10不用变
        //3  4    10    12  14  中间值 10不用变

        //看第4步之前 把前3步先理解了
        //第4步 改代码!
        int flag = 0;//建立一个是否+1的标志 默认加1
        int midflag = 0; //再建立一个对 中间值  是否要+1的标志
        int less = 0;//记录小于中间值的数量
        int more = 0;//记录大于中间值的数量
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] > median) more++;
            if (arr[i] < median) less++;
        }
        //  arr中 (大于中间值的数量)小于(小于中间值的数量）变成中间值    flag = 0
        //      例如： 3  4  6  10  10  14  变成10
        //  arr中 (大于中间值的数量)等于(小于中间值的数量）变成中间值+1  flag = 1
        //      例如： 6  10 12 15  20      变成13
        //  arr中 (大于中间值的数量)大于(小于中间值的数量）变成中间值+1  flag = 1
        //      例如： 3  10 10 10  12  14  变成11
        if (more >= less) flag = 1;
        //  arr中 (大于中间值的数量)小于(小于中间值的数量）时 中间值不用变 midflag = 0
        //3  4    10    12  14  中间值 10不用变    midflag = 0
        //  arr中 (大于中间值的数量)等于(小于中间值的数量）时 中间值不用变 midflag = 0
        //3  4    10    10  14  中间值 10不用变    midflag = 0
        //  arr中 (大于中间值的数量)大于(小于中间值的数量）时 中间值不用变 midflag = 1
        //3  10   10    12  14  中间值 10要变大    midflag = 1
        if (more > less) midflag = 1;

        //第4步  改变arr
        //循环arr与median比
        //使得全班刷题比他多的学生数 不超过 刷题比他少的学生数。
        for (int i = 0; i < arr.length; i++) {
            //3  10   10    12  14  中间值 10要变大
            //3  4    10    10  14  中间值 10不用变
            if (arr[i] < median) {
                //小于中间值的arr[i] 通过flag 分情况
                arr[i] = median + flag - arr[i];
            } else if (arr[i] == median && midflag == 1) {
                //等于中间值的arr[i]  通过midflag 分情况
                arr[i] = median + midflag - arr[i];
            } else {
                arr[i] = 0;
            }
        }

        //输出结果 注意：其元素中间有空格！！！
        for (int i = 0; i < arr.length - 1; i++) {
            System.out.print(arr[i] + " ");//不换行
        }
        System.out.print(arr[arr.length - 1]);

        //程序运行时间 = 程序结束时间-程序起始时间
        System.out.println("\n程序运行时间：" +
                (System.currentTimeMillis() - timeMillis) + "ms");
        //运行完 将多余输出语句删除！
    }
}

谢谢观看，这个可以在OJ(dotcpp)上跑满分

dotcpp 这个耗时是什么意思？如果是1473ms 那么就超时了，需要再次优化代码。55555