【前缀和+二分查找】

解题思路:

一.定义sum数组用来存刷题数小于i的人数

运用前缀和

二.

如果小于i题的人数小于大于i题的人数

那么必须在刷i+1,max题里找，看看到底刷到多少题才能躺的人大于等于卷的人

如果大于等于则不需要再刷了，值为0
注意事项:

参考代码:

import java.io.*;
import java.util.*;

/**
 * @Author:杨雨彤
 * @date:2024/2/5 17:02
 */
public class Main{
    static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
    static PrintWriter pw=new PrintWriter(new OutputStreamWriter(System.out));
    static int sum[];
    static  int n;
    static  int max;
    static int min;
    public static void main(String[] args) throws IOException {
         n=Integer.parseInt(br.readLine());
        sum=new int[100020];
        int []need=new int[n];
        int []ans=new int[n];
        int max=-1;
        int min=Integer.MAX_VALUE;
        String[] s = br.readLine().split(" ");
        int index;
        for (int i = 0; i < n; i++) {
            index=Integer.parseInt(s[i]);
            ans[i]=index;
            max=Math.max(max,index);
            min=Math.min(min,index);
            sum[index]++;
        }

        //sum[i]记录刷题数少于等于i题的人数,故sum[i-1]就是刷题数量小于i题的人数
        //前缀和
        for (int j =min+1; j <=max ; j++) {
                sum[j] = sum[j - 1] + sum[j] ;
            }
        for (int i= 0; i <n ; i++) {
            if(ans[i]<1){
                need[i]=0;
            }else if (sum[ans[i]-1]<n-sum[ans[i]]){
                int target = binSearch(ans[i]+1, max);
                need[i]=target-ans[i];
            }
        }
//
        for (int i = 0; i <n ; i++) {
            pw.print(need[i]+" ");
        }
        pw.flush();
        pw.close();
    }
    private static int binSearch(int l,int r){
       int res=Integer.MAX_VALUE;
       while(l<=r){
           int mid=(l+r)>>1;
           if(sum[mid-1]-1>=n-sum[mid]){//这里我们是想让这个人的成绩ans[i]变成mid,故在找刷题数小于mid题时要把这个人删去
               res=Math.min(res,mid);
               r=mid-1;
           }else{
               l=mid+1;
           }
       }
       return res;
    }
}