本文主要是介绍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());}}
}
这篇关于Codeforces Round 812 (Div. 2) ---- C. Build Permutation --- 题解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
