问题描述

小蓝老师教的编程课有 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.

代码

二分法比中位数快一倍。

import java.io.*;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class Main {
    static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static final PrintWriter print = new PrintWriter(System.out);
    static final StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    public static int nextInt() throws IOException {
        st.nextToken();
        return (int) st.nval;
    }


    public static void main(String[] args) throws IOException {
        int n = nextInt();
        int[] a = new int[n];
        int[] count = new int[100001];
        for (int i = 0; i < n; i++) {
            a[i] = nextInt();
            count[a[i]]++;
        }
        for (int i = 1; i <= 100000; ++i) {
            count[i] += count[i - 1];
        }
        for (int i = 0; i < n; ++i) {
            if (count[100000] - count[a[i]] <= count[Math.max(0,a[i]-1)]) {
                print.print(0 + " ");
                continue;
            }
            int l = a[i] + 1, r = 100000;
            while (l < r) {
                int mid = l + r >> 1;
                if (count[100000] - count[mid] <= count[mid - 1] - 1) r = mid;
                else l = mid + 1;
            }
            print.print((r - a[i]) + " ");
        }
        print.flush();
    }


}

import java.io.*;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class Main {
    static final Scanner sc = new Scanner(System.in);
    static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static final PrintWriter print = new PrintWriter(System.out);
    static final StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    public static int nextInt() throws IOException {
        st.nextToken();
        return (int) st.nval;
    }

    public static void main(String[] args) throws IOException {
        int n = nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = nextInt();
        }
        Integer[] b = new Integer[n];
        int[] ans = new int[n];
        for (int i = 0; i < n; i++)
            b[i] = i;
        Arrays.sort(b, Comparator.comparingInt(o -> a[o]));
        int len = n / 2;
        int c = a[b[len]];
        int l = len, r = len;
        while (l >= 0 && a[b[l]] == c) {
            l--;
        }
        while (r < n && a[b[r]] == c) {
            r++;
        }
        int d = 1;
        if (n - r > l + 1) {
            for (int i = l + 1; i < r; i++) {
                ans[b[i]] = a[b[r]] - a[b[i]];
            }
        }
        if(n-r <= l) {
            d = 0;
        }
        for (int i = 0; i < l + 1; i++) {
            ans[b[i]] = c - a[b[i]] + d;
        }

        print.print(ans[0]);
        for (int i = 1; i < n; i++) {
            print.print(" " + ans[i]);
        }
        print.flush();
    }

}