题解

问题描述

给定一个长度为 $n$ 的排列 $p = [p_1, p_2, \dots, p_n]$。称下标 $i$（$1 \le i < n$）为“好位置”，如果存在 $j$ 满足 $i < j \le n$ 且 $p_i > p_j$。记原排列中“好位置”的个数为 $G(p)$。

要求构造另一个排列 $q$，满足：

1. $q \neq p$；
2. $G(q) = G(p)$。

若存在，输出「YES」及一个满足条件的 $q$；否则输出「NO」。

思路

1. 特殊情况：当 $n < 3$ 时，排列长度太小，任意交换都会改变“好位置”数，因此无解，直接输出「NO」。

2. 寻找最右侧下降点：遍历下标 $i$ 从 $n-1$ 到 $1$（即 $i = n-2, n-3, \dots, 1$），寻找第一个满足 $p_i > p_{i+1}$ 的下标，记为 $\text{idx}$。如果不存在这样的下标，则原排列完全递增，无法构造不同且保持相同“好位置”数的 $q$，输出「NO」。

3. 局部交换构造：将 $p$ 复制为 $q$，然后：

   • 如果 $\text{idx} \le n-3$，交换 $q[\text{idx}]$ 与 $q[\text{idx}+2]$；
   • 否则（即 $\text{idx} = n-2$），交换 $q[\text{idx}-1]$ 与 $q[\text{idx}]$。

   这样仅在最右侧下降点附近进行一次交换，不会改变其他位置的“好位置”状态，且得到 $q \neq p$。

4. 输出答案：如上构造成功，则打印「YES」和 $q$；否则打印「NO」。

C++

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;  // 测试用例数量
    while (T--) {
        int n;
        cin >> n;  // 排列长度
        vector<int> a(n);
        for (int i = 0; i < n; ++i) {
            cin >> a[i];  // 读入原排列 p
        }

        // 情况1：n < 3 无解
        if (n < 3) {
            cout << "NO\n";
            continue;
        }

        // 寻找最右侧下降点 idx，使得 a[idx] > a[idx+1]
        int idx = -1;
        for (int i = n - 2; i >= 0; --i) {
            if (a[i] > a[i + 1]) {
                idx = i;
                break;
            }
        }
        // 如果没有下降点，排列已全增，无解
        if (idx < 0) {
            cout << "NO\n";
            continue;
        }

        // 复制为 q 并局部交换
        vector<int> b = a;
        if (idx <= n - 3) {
            // 交换 b[idx] 与 b[idx+2]
            swap(b[idx], b[idx + 2]);
        } else {
            // idx == n-2，交换 b[idx-1] 与 b[idx]
            swap(b[idx - 1], b[idx]);
        }

        // 输出结果
        cout << "YES\n";
        for (int i = 0; i < n; ++i) {
            cout << b[i] << (i + 1 < n ? ' ' : '\n');
        }
    }
    return 0;
}

Python

import sys
input = sys.stdin.readline

def solve():
    T = int(input())  # 测试用例数量
    for _ in range(T):
        n = int(input())  # 排列长度
        p = list(map(int, input().split()))  # 读入原排列 p

        # 情况1：n < 3 无解
        if n < 3:
            print("NO")
            continue

        # 寻找最右侧下降点 idx，使得 p[idx] > p[idx+1]
        idx = -1
        for i in range(n - 2, -1, -1):
            if p[i] > p[i + 1]:
                idx = i
                break

        # 如果没有下降点，排列已全增，无解
        if idx < 0:
            print("NO")
            continue

        # 构造 q 并局部交换
        q = p.copy()
        if idx <= n - 3:
            # 交换 q[idx] 与 q[idx+2]
            q[idx], q[idx + 2] = q[idx + 2], q[idx]
        else:
            # idx == n-2，交换 q[idx-1] 与 q[idx]
            q[idx - 1], q[idx] = q[idx], q[idx - 1]

        # 输出结果
        print("YES")
        print(*q)

if __name__ == '__main__':
    solve()

Java

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());  // 测试用例数量
        while (T-- > 0) {
            int n = Integer.parseInt(br.readLine());  // 排列长度
            int[] a = Arrays.stream(br.readLine().split(" "))
                            .mapToInt(Integer::parseInt)
                            .toArray();  // 读入原排列 p

            // 情况1：n < 3 无解
            if (n < 3) {
                System.out.println("NO");
                continue;
            }

            // 寻找最右侧下降点 idx，使得 a[idx] > a[idx+1]
            int idx = -1;
            for (int i = n - 2; i >= 0; --i) {
                if (a[i] > a[i + 1]) {
                    idx = i;
                    break;
                }
            }
            // 如果没有下降点，排列已全增，无解
            if (idx < 0) {
                System.out.println("NO");
                continue;
            }

            // 构造 q 并局部交换
            int[] b = a.clone();
            if (idx <= n - 3) {
                // 交换 b[idx] 与 b[idx+2]
                int tmp = b[idx];
                b[idx] = b[idx + 2];
                b[idx + 2] = tmp;
            } else {
                // idx == n-2，交换 b[idx-1] 与 b[idx]
                int tmp = b[idx - 1];
                b[idx - 1] = b[idx];
                b[idx] = tmp;
            }

            // 输出结果
            System.out.println("YES");
            for (int x : b) System.out.print(x + " ");
            System.out.println();
        }
    }
}

题目内容

小苯定义一个数组的“好位置”为：满足其右侧存在比其小的元素形式化的即:

在数组$a$中对于$1≤i<n$存在$1≤i<j≤n$使得$a_i>a_j$，则称$i$为“好位置”。

现在小苯有一个长度为$n$ 的排列$p$，他希望你构造一个长为n的排列$q$，满足$p≠q$同时$p,q$的“好位置”个数相同。

输入描述

本题包含多组测试数据。

第一行一个正整数$T(1≤T≤10000)$，表示测试数据的组数。

接下来对于每组测试数据，输入包含两行

第一行一个正整数$n(1≤n≤200000)$，表示排列$p$的长度。

第二行$n$个正整数$p_i(1≤p_i≤n)$，表示排列$p$。(保证输入是一个排列)

(保证所有测试数据中，$n$的总和不超过$200000$)

输出描述

输出包含$T$行，对于每组测试数据输出一行。

如果可以找到一个满足条件的$q$，则先输出一行一个字符串“$YES$”(不含双引号)，表示可以找到，再在下一行输出一行$n$个数字表示满足条件的排列q(有多解输出任意即可。)

如果找不到一个满足条件的$q$，则输出一个“$NO$”(不含双引号)。

样例1

输入

2 
4
2 1 3 4
3 
1 2 3

输出

YES
1 2 4 3
NO

说明

对于第一个测试数据:

$[2, 1, 3,4]$的"好位置”个数为$1$。(好位置有:$i=1$)

$[1,2,4,3]$的“好位置”个数也为$1$。(好位置有:$i=3$)