本文主要是介绍Codeforces Global Round 25 ---- F. Inversion Composition ---- 题解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
F. Inversion Composition：
题目描述：
思路解析：
有一个初始排列 p，然后现在让我们给出一个q排列数组，并通过p数组和q数组得到qp数组，问是否能得到某组q和qp数组使他们的逆序对数量之和为k。
假设p有一对 (i,j) 为 (pi,pj) -> (2,3)， 如果q2 < q3, 那么提供的答案贡献为0，否则会提供2的答案贡献。 假设p有一对 (i,j) 为 (pi,pj) -> (3,2) ， 如果p2 > p3,那么提供的答案贡献为1，否则还是提供1的答案贡献。 从这里可以分析出，p的逆序对数量应该和k奇偶性相同。
那么这样，我们就可以知道qp数组我们需要多少对逆序队了，利用这个来求得qp数组，再反解q数组，并且要保证p数组的逆序对要出现在qp中。
代码实现：
import java.io.*;
import java.math.BigInteger;
import java.util.*;public class Main {static int inf = (int) 1e9;static int[] t = new int[300005];public static void main(String[] args) throws IOException {int T = f.nextInt();while (T > 0) {solve();T--;for (int i = 1; i <= n; i++) {t[i] = 0;}}w.flush();w.close();br.close();}static int n;public static void solve() {n = f.nextInt();long k = f.nextLong();int[] a = new int[n];long m = 0;int[] cnt = new int[n];int[] ip = new int[n];for (int i = 0; i < n; i++) {a[i] = f.nextInt() - 1;ip[a[i]] = i;cnt[i] = sum(a[i]);m += i - cnt[i];upd(a[i] + 1, 1);}if (m > k || k > (long) (n-1) * n - m || (k - m) % 2 == 1){w.println("NO");return;}k = (k - m) / 2;int[] qp = new int[n+1];for (int i = 0; i < n; i++) {if (k > cnt[i]){k-=cnt[i];}else {for (int j = 0, v = i; j < i; j++) {qp[j] = v--;if (a[j] < a[i] && --k == 0){qp[i] = v--;}}for (int j = i+1; j < n; j++) {qp[j] = j;}break;}}w.println("YES");for (int i = 0;i < n; i++) {w.print(qp[ip[i]] + 1 + " ");}w.println();}static int lowbit(int x) {return x & -x;}static void upd(int x, int val){for (int i = x; i <= n; i+=lowbit(i)) {t[i] += val;}}static int sum(int x){int res = 0;for (int i = x; i >= 1; i-=lowbit(i)) {res += t[i];}return res;}static PrintWriter w = new PrintWriter(new OutputStreamWriter(System.out));static Input f = 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 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 Global Round 25 ---- F. Inversion Composition ---- 题解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
