Mr.Clutch


私信TA

用户名:uq_63396757599

访问量:814

签 名:

等  级
排  名 3721
经  验 1367
参赛次数 0
文章发表 19
年  龄 0
在职情况 学生
学  校
专  业

  自我简介:

解题思路:

排序+枚举

注意事项:

考试时候想得太复杂了。。。用了权值线段树去暴力模拟,果然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;
    }
}


 

0.0分

3 人评分

  评论区