Codeforces Round 812 (Div. 2) ---- C. Build Permutation --- 题解

目录

C. Build Permutation

题目描述：

​编辑 思路解析：

代码实现：

---

C. Build Permutation

题目描述：

        

 思路解析：

        先证明在任何情况下答案均存在。

        假设我们所求的为 m m+1 m+2.....n 的排列，我们称不小于n的最小平方数为h，不大于n的最大平方数为w。那么h和w之间的差值为根号w+根号h一定小于n，则 h <= 2 * n,那么 h-n <= n.

        因此pi = h-i，我们可以将它填充为h   h-k<=i<=k,利用这种方法可以递归地把k还原为-1

代码实现：

import java.io.*;
import java.math.BigInteger;
import java.util.*;public class Main {static int[] arr;public static void main(String[] args) throws IOException {int t = input.nextInt();for (int o = 0; o < t; o++) {int n = input.nextInt();arr = new int[n];recurse(n - 1);for (int i = 0; i < n; i++) {pw.print(arr[i] + " ");}pw.println();}pw.flush();pw.close();br.close();}public static void recurse(int r){if (r < 0) return;int t = (int) Math.sqrt(2 * r);t *= t;int l = t - r;recurse(l - 1);for (; l <= r; l++, r--) {arr[l] =r;arr[r] = l;}}static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));static Input input = new Input(System.in);static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));static class Input {public BufferedReader reader;public StringTokenizer tokenizer;public Input(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 String nextLine() {String str = null;try {str = reader.readLine();} catch (IOException e) {// TODO 自动生成的 catch 块e.printStackTrace();}return str;}public int nextInt() {return Integer.parseInt(next());}public long nextLong() {return Long.parseLong(next());}public Double nextDouble() {return Double.parseDouble(next());}public BigInteger nextBigInteger() {return new BigInteger(next());}}
}