题解2673: 蓝桥杯2022年第十三届省赛真题-最少刷题数（JAVA题解）

解题思路:

排序+枚举

注意事项:

考试时候想得太复杂了。。。用了权值线段树去暴力模拟，果然TLE。

本题首先需要对输入按值降序排序，之后可以看做不断将对称轴后的数向前插入，当然，为了节约时间，可以直接插入至对称轴处。

为此，我们需要判断插入到对称轴之前才满足条件，还是插入到与对称轴相同就满足条件（注意，插入时后面有一个数已经被取缔了需要-1）

此外，要注意对称轴可能由多个相同的数组成，因此需要判断边界。

参考代码:

import java.io.*;
import java.util.*;
public class Main {
    static class Pair implements Comparable<Pair>{
        int index;
        int value;

        Pair(int value, int index){
            this.value = value;
            this.index = index;
        }

        public int compareTo(Pair other){
            return  other.value - this.value;
        }
    }
    static StreamTokenizer cin;
    static PrintWriter out;
    static int N;  // 学生总数
    static Pair[] arr;
    static int[] res;
    public static void main(String[] args) throws IOException{
        cin = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        out = new PrintWriter(new OutputStreamWriter(System.out));
        N = nextInt();
        arr = new Pair[N];
        res = new int[N];
        for(int i = 0; i < N; i++){
            int num = nextInt();
            arr[i] = new Pair(num, i);
        }

        Arrays.sort(arr);  // 降序
        int axis = N%2==0?N/2-1:N/2;  // 初始化对称轴
        int axisV = arr[axis].value;
        int s = axis;
        int e = axis;
        for(; s!=-1 && arr[s].value==axisV; s--);
        for(; e!=N && arr[e].value==axisV; e++);
        boolean flag = false;
        int bigger = s+1;
        int smaller = N-e;
        if(bigger <= smaller)
            flag = true;  // 对称轴附近不需要更改
        int index = e;
        if(!flag)
            index = s+1;
        for(int i = index; i < N; i++){
            if(s+1 <= N-e-1){
                res[arr[i].index] = arr[axis].value-arr[i].value;
            }else{
                res[arr[i].index] = arr[axis].value-arr[i].value+1;
            }
        }
        boolean first = true;
        for(int i = 0; i < N; i++){
            if(first){
                out.print(res[i]);
                first = false;
                continue;
            }
            out.print(" "+res[i]);
        }
        out.flush();
        out.close();



    }

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