思路

• 关键等价：若在某次操作中选择的位置的值分别为 $v$ 与 $v+1$，则操作后它们交换位置；否则不可能保持为排列。 证明要点：多重集计数平衡要求对 $a\to a+1$ 与 $b\to b-1$ 的四个计数改变量相互抵消，只有当 $b=a+1$ 时成立。

• 因而，允许的操作等价于“交换值为相邻数对 $(v, v+1)$ 的两个位置”，这就是在“值空间”的相邻换位。

• 设 $\text{pos}[v]$ 为值 $v$ 的当前位置，则当且仅当 $\text{pos}[v] > \text{pos}[v+1]$ 时，$(v, v+1)$ 构成一对“逆序”。每次交换 $(v, v+1)$ 会恰好使逆序数减少 $1$。

• 令

  $\text{inv}(p)$=$\left|{(i,j)\mid 1\le i<j\le n,\ p_i>p_j}\right|$

  则最少操作次数为

  $$k_{\min}=\text{inv}(p).$$

• 构造方法：对 $v=1\dots n-1$ 反复检查，当 $\text{pos}[v]>\text{pos}[v+1]$ 时，交换它们并记录操作，直到所有相邻值在位置上按顺序出现为止。等价于对 $\text{pos}[1],\dots,\text{pos}[n]$ 做冒泡排序。

C++

#include <bits/stdc++.h>
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	if (!(cin >> n)) return 0;
	vector<int> p(n + 1), pos(n + 1); // 使用1-based
	for (int i = 1; i <= n; ++i) {
		cin >> p[i];
		pos[p[i]] = i; // 记录值v所在的位置
	}

	vector<pair<int,int>> ops; // 记录操作 (x,y): x加一，y减一 => 交换值v与v+1
	bool changed = true;
	while (changed) {
		changed = false;
		for (int v = 1; v <= n - 1; ++v) {
			while (pos[v] > pos[v + 1]) {
				int i = pos[v];     // 位置i上是v
				int j = pos[v + 1]; // 位置j上是v+1
				ops.emplace_back(i, j);
				// 执行交换：操作等价于把i位置+1，j位置-1
				swap(p[i], p[j]);
				// 更新pos
				pos[v] = j;
				pos[v + 1] = i;
				changed = true;
			}
		}
	}

	cout << ops.size() << '\n';
	for (auto &op : ops) {
		cout << op.first << ' ' << op.second << '\n';
	}
	return 0;
}

Python

import sys

def main():
	data = sys.stdin.read().strip().split()
	if not data:
		return
	it = iter(data)
	n = int(next(it))
	p = [0] + [int(next(it)) for _ in range(n)]  # 1-based
	pos = [0] * (n + 1)
	for i in range(1, n + 1):
		pos[p[i]] = i  # 记录值v所在的位置

	ops = []  # 记录操作 (x, y)

	changed = True
	while changed:
		changed = False
		for v in range(1, n):
			while pos[v] > pos[v + 1]:
				i, j = pos[v], pos[v + 1]  # i位置是v，j位置是v+1
				ops.append((i, j))
				# 执行交换（一次合法操作等价于交换值v与v+1）
				p[i], p[j] = p[j], p[i]
				pos[v], pos[v + 1] = j, i
				changed = True

	out = []
	out.append(str(len(ops)))
	for x, y in ops:
		out.append(f"{x} {y}")
	sys.stdout.write("\n".join(out))

if __name__ == "__main__":
	main()

Java

import java.io.*;
import java.util.*;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String s = br.readLine();
		if (s == null || s.trim().isEmpty()) return;
		int n = Integer.parseInt(s.trim());
		int[] p = new int[n + 1];     // 1-based
		int[] pos = new int[n + 1];   // pos[v] = 位置
		String[] parts = br.readLine().trim().split("\\s+");
		for (int i = 1; i <= n; i++) {
			p[i] = Integer.parseInt(parts[i - 1]);
			pos[p[i]] = i;
		}

		List<int[]> ops = new ArrayList<>(); // 记录操作 (x,y)

		boolean changed = true;
		while (changed) {
			changed = false;
			for (int v = 1; v <= n - 1; v++) {
				while (pos[v] > pos[v + 1]) {
					int i = pos[v];     // i位置是v
					int j = pos[v + 1]; // j位置是v+1
					ops.add(new int[]{i, j});
					// 交换值v与v+1（一次合法操作）
					int tmp = p[i]; p[i] = p[j]; p[j] = tmp;
					// 更新位置
					pos[v] = j;
					pos[v + 1] = i;
					changed = true;
				}
			}
		}

		StringBuilder sb = new StringBuilder();
		sb.append(ops.size()).append('\n');
		for (int[] op : ops) {
			sb.append(op[0]).append(' ').append(op[1]).append('\n');
		}
		System.out.print(sb.toString());
	}
}

题目内容

给定长度为 $n$ 的排列 {$p_1,p_2,…,p_n$}，定义一次操作为：

选择两个不同的位置 $i,j$ ，将 $p_i$ 增加 $1$ ，同时将 $P_j$ 减少 $1$ ;同时需要保证每次操作后，数组仍是 $1$ 到 $n$ 的一个排列。

问将数组变为严格递增排列 {$1,2,…,n$} 需要的最少操作次数。

长度为 $n$ 的排列是由 $1,2,...,n$ 这 $n$ 个整数、按任意顺序组成的数组(每个整数均恰好出现一次)。例如，{$2,3,1,5,4$} 是一个长度为 $5$ 的排列，而 {$1,2,2$} 和 {$1,3,4$} 都不是排列，因为前者存在重复元素，后者包含了超出范围的数。

输入描述

第一行输入整数 $n(1≤n≤10^3)$ 表示排列长度；

第二行输入 $n$ 个整数 $p_1,p_2,...,p_n(1≦p_i≦n)$ ，它们构成 $1$ 到 $n$ 的个排列。

输出描述

第一行输出一个整数 $k$ ，表示需要的最少操作次数。

此后 $k$ 行，第 $i$ 行输出两个整数 $x_i,y_i(1≦x_i,y_i≦n;x_i≠y_i)$ ，表示第 $i$ 次操作将 $P_{x_i}$ 増加 $1$ ，$P_{y_i}$ ; 减少 $1$ .

如果存在多个解决方案，您可以输出任意一个，系统会自动判定是否正确。注意，自测运行功能可能因此返回错误结果，请自行检查答案正确性。

样例1

输入

3
3 2 1

输出

3
3 2
3 1
2 1

说明

在这个样例中，初始排列为 {$3,2,1$}：

第一次操作 $(x_1= 3,y_1= 2)$ 后排列变为 {$3,1,2$} ；

第二次操作 $(x_2= 3,y_2 = 1)$ 后排列变为 {$2,1,3$} ；

第三次操作 $(x_3= 2,y_3 = 1)$ 后排列变为 {$1,2,3$} ；

综上，通过 $3$ 次操作将排列变为严格递增排列 ${1,2,3}$ 。我们可以证明，这是最少需要的操作次数。

样例2

输入

1
1

输出

0