java最少刷题数

ゝ一纸荒年。 2024-03-26 12:24 56阅读 0赞

问题描述  
小蓝老师教的编程课有  
�  
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] + " ");
                }
            }
        }
    
    }