题解 | #小美的排列构造#

题意

要求构造一个排列 ，在这个排列中，每个相邻项的和记为 ，记 的最大值为 ，最小值为 ，要使得 最小的一个序列。

思路

我们的目的是让相邻的两项和尽可能接近，比较容易想到等差公式中的“首项加末项”。例如， 的情况：

• 先取 1 和 5，得到的和是 6。此时序列为 ；
• 再取 2 和 4，得到的和也是 6。此时序列为 或 ，比较下，显然 相邻和极差更小些；
• 最后取 3，得到的序列为 ，可以检验，相邻和为 ，极差为 。

因此，对于任何一个序列，我们都可以采用这种方法构造出相邻和极差为 的序列。

具体做法，可以使用 双指针 来分别指向当前自然排列（从小到大）的最大值最小值，然后依次放入序列中即可。

import java.io.*;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.util.*;

import static java.util.Arrays.deepToString;


public class Main {

    static boolean LOCAL = Boolean.parseBoolean(System.getenv("LOCAL"));
    static boolean TO_FILE = Boolean.parseBoolean(System.getenv("LOCAL"));
    static Scanner sc = new Scanner(System.in);
    static void debug(Object... os) {
        System.err.println(deepToString(os));
    }

    public static void main(String[] args) {

        if (LOCAL) {
            try {
                System.setIn(new FileInputStream("./data/in.txt"));
            } catch (Throwable e) {
                LOCAL = false;
            }
        }

        if (TO_FILE) {
            try {
                System.setOut(new PrintStream("./data/output.txt"));
            } catch (FileNotFoundException e) {
                e.printStackTrace();
            }
        }

        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        Task solver = new Task();
        solver.solve(in, out);
        out.close();
    }

    static class Task {
        Random random = new Random(751454315315L + System.currentTimeMillis());
        static final int MAXN = (int)1e6 + 10;
        static final long INF = (long)1e18;
        static final double EPS = 1e-7;
        static final double PI = Math.acos(-1.0);
        static final long MOD = (long)1e9 + 7;

        public void solve(InputReader in, PrintWriter out) {
            int t = 1;
//            t = in.nextInt();
            while (t-- > 0) {
                solveSingle(in, out);
            }
        }

        public void solveSingle(InputReader in, PrintWriter out) {
            int n = in.nextInt();
            boolean flag = true;
            int l = 1, r = n;
            for (int i = 0; i < n; i++) {
                if (flag) {
                    out.print(l++ + " ");
                } else {
                    out.print(r-- + " ");
                }
                flag = !flag;
            }
        }

    }

    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

        public double nextDouble() {
            return Double.parseDouble(next());
        }

        public float nextFloat() {
            return Float.parseFloat(next());
        }

        public BigDecimal nextBigDecimal() { return new BigDecimal(next()); }

        public String nextLine(){
            while (tokenizer == null || !tokenizer.hasMoreElements()){
                try{
                    tokenizer = new StringTokenizer(reader.readLine());
                }catch (IOException e){
                    e.printStackTrace();
                }
            }
            return tokenizer.nextToken("\n");
        }

    }
}

复杂度分析

• 时间复杂度： ，其中 为排列的大小。
• 空间复杂度：，不需要额外的数组来存储。