$\texttt{ABC178-F}$

题目描述

给定两个升序排序的长度为 $n$ 的序列 $A, B$，问是否可以将序列 $B$ 重新排列，使得对于每个 $i$，有$A _ i \neq B _ i$

如果可以，输出重新排序后的 $B$ 序列

输入格式

输入共三行

第一行有一个正整数 $n$

第二行有 $n$ 个整数，第 $i$ 个整数表示 $A _ i$

第三行有 $n$ 个整数，第 $i$ 个整数表示 $B _ i$

输出格式

如果没有满足条件的 $B$ 的排列，输出 No

否则在第一行输出 Yes，第二行输出序列 $B$

如果有多组解，输出其中任意一组即可

输入样例 $1$

6
1 1 1 2 2 3
1 1 1 2 2 3

输出样例 $1$

Yes
2 2 3 1 1 1

输入样例 $2$

3
1 1 2
1 1 3

输出样例 $2$

No

输入样例 $3$

4
1 1 2 3
1 2 3 3

输出样例 $3$

Yes
3 3 1 2

算法

(贪心,双指针) $O(n)$

结论：将 $B$ 按降序排序后，$B$ 中最多只会有一段 $B[l \sim r]$ 与 $A[l \sim r]$ 是相同的，且 $A[l \sim r]$ 和 $B[l \sim r]$ 中所有值都等于同一个数

证明：
我们假设将 $B$ 按倒序排序后，$B$ 中与 $A$ 相同的有两段

即存在一组 $[l _ 1, r _ 1], [l _ 2, r _ 2]$，满足 $\left\\{ \begin {aligned} & l _ 2 < r _ 1 \\\ & B[l _ 1, r _ 1] = A[l _ 1, r _ 1] \\\ & B[l _ 2, r _ 2] = A[l _ 2, r _ 2] \\\ & B[r _ 1 + 1, l _ 2 - 1] \neq A[r _ 1 + 1, l _ 2 - 1] \\\ \end {aligned} \right. $

因为 $A$ 是按升序排序的，所以 $A[l _ 2] \geq A[r _ 1]$

因为 $A[l _ 2] = B[l _ 2], A[r _ 1] = B[r _ 1]$，所以 $B[l _ 2] \geq B[r _ 1]$

因为 $B$ 是按降序排序的，所以 $B[l _ 2] \leq B[r _ 1]$

所以 $B[l _ 2] = B[r _ 1]$，同理 $B[l _ 2] = B[r _ 1]$

又因为 $A$ 和 $B$ 都具有单调性，所以 $A[r _ 1 \sim l _ 2], B[r _ 1 \sim l _ 2]$ 都是同一个数

所以 $A[r _ 1 \sim l _ 2] = B[r _ 1 \sim l _ 2]$

不满足假设，原命题证毕

根据这个结论，我们可以先将 $B$ 翻转，然后找到 $B$ 中和 $A$ 相同的一段 $[l, r]$，然后判断是否能用 $B$ 中其它的数替换掉 $B[l \sim r]$ 这一段

如果不能，输出 No，否则替换掉并输出

时间复杂度

根据结论，我们只需要找出 $A$ 中第一个和 $B$ 相同的数，然后试图替换即可

查找是 $O(n)$ 的，替换也可以做到 $O(n)$，所以总时间复杂度是 $O(n)$ 的

C++ 代码与注释

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 200005;

int n;
int a[N], b[N];

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++ ) cin >> a[i];
    for (int i = 0; i < n; i ++ ) cin >> b[n - i]; // 读入并将 B 翻转

    bool success = true; // 标记是否有合法的 B 的重排

    // 找第一个 a[i] == b[i] 的 i
    // 如果找到之后 success 被更新成 false 了，直接跳出
    for (int i = 1; i <= n && success; i ++ )
        if (a[i] == b[i])
        {
            // 这里要试图将 B 和 A 中相等的一段，用 B 的其它元素替换掉
            // 如果 a[i] 和 b[i] 不相等了，说明是 B 中和 A 相等的部分替换完了，直接跳出
            for (int k = 1; k <= n && a[i] == b[i]; k ++ )
            // 如果找到了 B 中的一个元素 b[k], 满足将 b[k] 与 b[i] 交换之后， a[k] != b[k] 且 a[i] != b[i]，
                if (b[k] != b[i] && a[k] != b[i])
                    swap(b[i], b[k]), i ++ ; // 那么将 b[i] 与 b[k] 交换，并让 i 走到下一个要替换的位置

            // 如果试图替换后 b[i] 仍与 a[i] 相同，说明不存在一组合法答案，让 success = false
            if (a[i] == b[i]) success = false;
        }

    puts(success ? "Yes" : "No");
    if (success) for (int i = 1; i <= n; i ++ ) cout << b[i] << ' '; 

    return 0;
}

顺便说一下做这道题的历程吧

这场 $\text{ABC}$ 打到 $\text{32min}$ 就过 $\text{E}$ 题了，感觉应该能过 $\text{F}$

结果看了题之后想了半天一点思路都没有。。我低估了 $\text{F}$ 题的难度

比赛还剩 $\text{2min}$ 的时候才猜到结论，写完代码比赛已经结束 $\text{4min}$ 了。。

差亿点点就 $\text{AK}$ 了。。我枯了。。。

我一共就打过四把 $\text{ABC}$，四把都被卡在了 $\text{F}$ 题。。

结语：wtcl