最少刷题数

最少刷题数

题目分析

对于每一名同学计算还需要再刷多少题才能保证刷题数比他多的人数不超过刷题数比他少的学生人数。我们可以考虑统计每一个分数的前缀和数组，sum[i]表示当前学生中，刷题数小于等于i的人数。那么对于学生i的刷题数a[i]，sum[a[i]-1]表示刷题数比该同学少的人数，n-sum[a[i]]+1表示刷题数比该同学多的人数，这里的+1是因为减掉了该同学本身，所以要再加回来。我们可以通过sum[a[i]-1]与n-sum[a[i]]的大小来判断该学生是否需要再刷题。

如果sum[a[i]-1]>=n-sum[a[i]]，说明该同学不需要再刷题，

如果sum[a[i]-1]<n-sum[a[i]]，说明该同学需要再刷题，那么需要刷多少道题呢？我们只需要找到满足sum[x-1]>=n-sum[x]的最小的x就可以了。其实这个x是固定的，那么我们要怎么找这个x呢？就是遍历一遍sum数组即可。

寻找满足sum[pos-1]>=n-sum[pos]的最小的pos

for(int i = 1;i <= maxn;i++) {
    if(cnt[i-1]-1>=n-cnt[i]) {
        pos = i;
        break;
    }
}

遍历所有学生的刷题数，如果sum[a[i]-1]>=n-sum[a[i]]，说明该同学不需要再刷题，打印0，否则打印当前刷题数和pos之间的差值。

for(int i = 1 ; i <= n ; i ++) {
    if(a[i]==0) System.out.print(pos-a[i] + " ");//注意刷题数为0时要特判不然会数组越界
    else {
        if(cnt[a[i]-1]>=n-cnt[a[i]]) 
        System.out.print(0 + " ");
        else
        System.out.print(pos-a[i] + " ");
	}
}

题目代码

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] ;
        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 ++) {
            cnt[i] += cnt[i - 1] ;
        }
        int pos = -1;
        for(int i = 1;i <= maxn;i++) {
        	if(cnt[i-1]-1>=n-cnt[i]) {
        		pos = i;
        		break;
        	}
        }
        for(int i = 1 ; i <= n ; i ++) {
        	if(a[i]==0) System.out.print(pos-a[i] + " ");//注意刷题数为0时要特判不然会数组越界
        	else {
        		if(cnt[a[i]-1]>=n-cnt[a[i]]) 
            	  System.out.print(0 + " ");
                else
				  System.out.print(pos-a[i] + " ");
          }
        }
    }
}