nlogn(排序),前缀和解法蓝桥杯2022年第十三届省赛真题-最少刷题数,

解题思路:
利用一个100000的数组存每个数字出现的次数,然后使用前缀和一次,计算出前缀和之后就能在O(1)的复杂度的时间内求出比当前

小的数有几个,相等的有几个,大的有几个

排序后找出中位数

判断当前数是否符合刷题数,满足则输出0

不满足则判断当前数到中位数是否符合题意,

如果不符合则将该数字增加到中位数+1即可
注意事项:

参考代码:

import java.io.BufferedReader;

import java.io.BufferedWriter;

import java.io.IOException;

import java.io.InputStreamReader;

import java.io.OutputStreamWriter;

import java.io.StreamTokenizer;

import java.util.Arrays;

public class Main {

    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static StreamTokenizer sc = new StreamTokenizer(br);

    public static BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));

    public static int nextInt() throws IOException {

        sc.nextToken();

        return (int) sc.nval;

    }

    public static int N, arr[];

    public static int n[] = new int[100010];

    public static void main(String[] args) throws IOException {

        N = nextInt();

        arr = new int[N + 1];

        int t[] = new int[N + 1];

        for (int i = 1; i <= N; i++) {

            arr[i] = nextInt();

            t[i] = arr[i];

            n[arr[i]]++;

        }

        for (int i = 1; i <= 100005; i++) {

            n[i] = n[i] + n[i - 1];

        }

        Arrays.sort(t);

        int mid = t[N / 2 + 1];

        int minmid = n[mid - 1];

        int equalmid = n[mid] - n[mid - 1];

        int maxmid = n[100005] - n[mid];

        for (int i = 1; i <= N; i++) {

            int c = arr[i];

            int min = n[c - 1];

            int equal = n[c] - n[c - 1];

            int max = n[100005] - n[c];

            if (max <= min) { // 如果符合题意

                out.write(Integer.toString(0));

                out.write(" ");

                continue;

            } // 如果当前数是中位数,加1即可

            if (max <= min + equal - 1) {

                out.write(Integer.toString(1));

                out.write(" ");

                continue;

            }

            // t[i]变到mid就行

            if (maxmid <= minmid - 1) {

                out.write(Integer.toString(mid - arr[i]));

                out.write(" ");

                continue;

            }

            // t[i]变到mid+1才行

            out.write(Integer.toString(mid - arr[i] + 1));

            out.write(" ");

        }

        out.flush();

    }

}

// 12 1 2 2 3 5 5 5 5 6 7 8 9