题解：AT_agc058_a [AGC058A] Make it Zigzag

题目传送门

题目链接

证明

结论：

1. 对于每个奇数位置 $i = 1, 3, 5, \cdots, 2N-1$，有 $P_i < P_{i+1}$。
2. 对于每个偶数位置 $i = 2, 4, 6, \cdots, 2N-2$，有 $P_i > P_{i+1}$。

证明：

• 我们需要将排列 $P$ 转换为“Zigzag”形式，即奇数位置的值小于其下一个值，偶数位置的值大于其下一个值。
• 每次操作可以交换相邻的两个元素，因此我们可以通过局部调整来满足条件。

• 我们从左到右依次检查每个位置 $i$：
  • 如果 $i$ 是奇数位置，且 $P_i > P_{i+1}$，则交换 $P_i$ 和 $P_{i+1}$。
  • 如果 $i$ 是偶数位置，且 $P_i < P_{i+1}$，则交换 $P_i$ 和 $P_{i+1}$。
• 这样，每次操作都确保当前位置满足“Zigzag”条件，且不会破坏之前已经满足条件的位置。

• 每个位置最多只需要一次交换操作。
• 由于总共有 $2N$ 个元素，而每次操作涉及两个相邻元素，因此最多需要 $N$ 次操作。

• 通过上述方法，我们可以确保每个奇数位置 $i$ 满足 $P_i < P_{i+1}$，每个偶数位置 $i$ 满足 $P_i > P_{i+1}$。
• 由于每次操作只影响当前和下一个元素，不会影响之前已经满足条件的位置，因此最终排列一定满足“Zigzag”条件。

• 以样例输入1为例：
  • 初始排列：$P = (4, 3, 2, 1)$。
  • 检查位置1（奇数）：$4 > 3$，交换后 $P = (3, 4, 2, 1)$。
  • 检查位置2（偶数）：$4 > 2$，无需交换。
  • 检查位置3（奇数）：$2 > 1$，交换后 $P = (3, 4, 1, 2)$。
  • 最终排列满足“Zigzag”条件。

总结：

思路

1. 让 $i$ 从 $1$ 循环到 $2N−1$，每次加上 $2$，如果 $P[i] \geq P[i+1]$，那么就交换。
2. 同样地，将 $i$ 从 $2$ 循环到 $2N−2$，每次加上 $2$，如果 $P[i] \le P[i+1]$，那么也交换。

代码

#include<iostream>
using namespace std;

int p[200005], ans[200005];

int main() {
    int n, cnt = 0;
    cin >> n;
    n *= 2;

    // 输入数组
    for (int i = 1; i <= n; i++) {
        cin >> p[i];
    }

    // 处理偶数位置
    for (int i = 2; i <= n - 2; i += 2) {
        if (p[i] <= p[i + 1]) {
            swap(p[i], p[i + 1]);
            ans[++cnt] = i;
        }
    }

    // 处理奇数位置
    for (int i = 1; i <= n - 1; i += 2) {
        if (p[i] >= p[i + 1]) {
            swap(p[i], p[i + 1]);
            ans[++cnt] = i;
        }
    }

    // 输出结果
    cout << cnt << endl;
    for (int i = 1; i <= cnt; i++) {
        cout << ans[i] << " ";
    }

    return 0;
}

代码说明

1. 输入部分：
   • 读取 $n$ 并将其乘以 $2$，表示数组的长度。
   • 读取数组 p[] 的值。
2. 处理偶数位置：
   • 遍历偶数位置 i，如果 p[i] <= p[i+1]，则交换这两个元素，并记录交换的位置。
3. 处理奇数位置：
   • 遍历奇数位置 i，如果 p[i] >= p[i+1]，则交换这两个元素，并记录交换的位置。
4. 输出结果：
   • 输出交换的次数 cnt。
   • 输出所有交换的位置。

示例

输入：

3
1 2 3 4 5 6

输出：

2
2 1

复杂度分析

• 时间复杂度：$O(n)$，其中 n 是数组的长度。
• 空间复杂度：$O(n)$，用于存储交换的位置。