题目详情题解（0）讨论（0）提交记录（0）

AT_abc350_c.[ABC350C] Sort

普及-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给定一个是 $ (1,2,\ldots,N) $ 的排列的数列 $ A=(A_1,\ldots,A_N) $。
你可以进行 $ 0 $ 次到 $ N-1 $ 次操作，将 $ A $ 变为 $ (1,2,\ldots,N) $。

  • 操作：可以自由选择满足 $ 1\leq i < j \leq N $ 的整数对 $ (i,j) $，交换 $ A $ 的第 $ i $ 个和第 $ j $ 个元素。

在题目给定的限制条件下，总是可以将 $ A $ 变为 $ (1,2,\ldots,N) $，这一点可以得到证明。

输入格式

输入从标准输入按以下格式给出。

$ N $ $ A_1 $ $ \ldots $ $ A_N $

输出格式

设操作次数为 $ K $，请输出 $ K+1 $ 行。
第 $ 1 $ 行输出 $ K $。
第 $ l+1 $ 行（$ 1\leq l \leq K $）输出第 $ l $ 次操作选择的整数 $ i,j $，用空格隔开。
只要满足题目条件，任意一种输出都被视为正确答案。

输入输出样例

  • 输入#1

    5
3 4 1 2 5

    输出#1

    2
1 3
2 4

  • 输入#2

    4
1 2 3 4

    输出#2

    0

  • 输入#3

    3
3 1 2

    输出#3

    2
1 2
2 3

说明/提示

限制条件

  • $ 2 \leq N \leq 2\times 10^5 $
  • $ (A_1,\ldots,A_N) $ 是 $ (1,2,\ldots,N) $ 的一个排列
  • 输入均为整数

样例解释 1

通过操作，数列会如下变化：

  • 初始时 $ A=(3,4,1,2,5) $。
  • 第 1 次操作交换第 1 个和第 3 个元素，$ A=(1,4,3,2,5) $。
  • 第 2 次操作交换第 2 个和第 4 个元素，$ A=(1,2,3,4,5) $。

除此之外，以下输出也是正确答案：

4
2 3
3 4
1 2
2 3

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页