java最少刷题数

问题描述
小蓝老师教的编程课有
�
N 名学生, 编号依次是
1
…
�
1…N 。第
�
i 号学生这学期 刷题的数量是
�
�
A
i
​
。

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

输入格式
第一行包含一个正整数
�
N 。

第二行包含
�
N 个整数:
�
1
,
�
2
,
�
3
,
…
,
�
�
A
1
​
,A
2
​
,A
3
​
,…,A
N
​
.

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

样例输入
5
12 10 15 20 6
copy
样例输出
0 3 0 0 7
copy
评测用例规模与约定
对于
30
%
30% 的数据,
1
≤
�
≤
1000
,
0
≤
�
�
≤
1000
1≤N≤1000,0≤A
i
​
≤1000.

对于
100
%
100% 的数据,
1
≤
�
≤
100000
,
0
≤
�
�
≤
100000
1≤N≤100000,0≤A
i
​
≤100000.

运行限制
最大运行时间：1s
最大运行内存: 512M

import java.util.Collections;
import java.util.Scanner;
import java.io.*;

public class Main {
   
    static final int N = 100000 ;//最多刷题人数
    public static void main(String[] args) throws IOException {
   
        StreamTokenizer in= new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));//快读
        in.nextToken() ;
        int n = (int)in.nval ;//读入学生的数量
        int a[] = new int[n + 1] ;//用来放每个学生的刷题数量，从1开始放
        int cnt[] = new int[N + 1] ;//用来放前缀和
        int maxn = 0 ;//在后面的循环中降低上记
        //读入每个学生的刷题数
        for(int i = 1 ; i <= n ; i ++) {
   
            in.nextToken();
            a[i] = (int)in.nval ;
            cnt[a[i]] ++ ;//每个刷题数的人数
            maxn = Math.max(maxn , a[i]) ;//记住最大的刷题数量
        }
        //求前缀和
        for(int i = 1 ; i <= maxn ; i ++) {
   
        	//刷题数量小于等于i的数量是
            cnt[i] += cnt[i - 1] ;
        }
        
        //计算每一个学生至少还要刷多少道题才能达标
        int pos = -1 ;//学生补到新的达标的中位数
        int pos1 = -1 ;//输入这些刷题数的中位数
        for(int i = 1 ; i <= maxn ; i ++) {
   
        	//刷题数比i少的人在cnt[i - 1]，如果大于等于n - cnt[i]，那么i就是我们要找的中位数
            if(cnt[i - 1] >= n - cnt[i]) {
   
            	//只记住第一个满足条件的i，
                if(pos1 == -1) pos1 = i ;
            }
            //补题后新的中位数
            if(cnt[i - 1] - 1 >= n - cnt[i]) {
   
                if(pos == -1) {
   
                    pos = i ;
                    break ;
                }
            }
        }
        if(pos == -1) {
   
            for(int i = 1 ; i <= n ; i ++) {
   
                System.out.print("0 ") ;
            }
        }else {
   
            for(int i = 1 ; i <= n ; i ++) {
   
                if(a[i] >= pos1) System.out.print("0 ");
                else System.out.print(pos - a[i] + " ");
            }
        }
    }

}