【AtCoder】Contrast

題目連結

時間複雜度

• $O(N)$

解題想法

首先用 C++ 的官方函式 reverse() 反轉

$B$，因為

$B$ 在反轉前是遞增數列，所以想當然反轉之後就會變成遞減數列

此時，我們可以發現

$A$ 和

$B$ 只有可能在中間一個區間存在連續的相同元素，這時候我們就可以從頭開始掃過數列，直到重複的區間全部被替換掉

掃完之後只可能出現兩種情況： 1. 找出一個正解字串 2. 無法完成一個正解字串

這時候再配合 if 判斷一下就可以解決了

完整程式

值得注意的地方是最後判斷那邊要記得考慮到沒有重複區間的狀態，不要不小心誤判了

/* Question : AtCoder Beginner Contest 178 - F - Contrast */

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

#define opt ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define pirq(type) priority_queue<type, vector<type>, greater<type>>
#define mem(x, value) memset(x, value, sizeof(x));
#define pii pair<int, int>
#define pdd pair<double, double>
#define pb push_back
#define f first
#define s second
#define int long long

const auto dir = vector< pair<int, int> > { {1, 0}, {0, 1}, {-1, 0}, {0, -1} };
const int MAXN = 2e5 + 50;
const int Mod = 1e9 + 7;
int n, flag, l, r, len, cnt, a[MAXN], b[MAXN];

signed main(){
    opt;
    cin >> n;
    for( int i = 0 ; i < n ; i++ ) cin >> a[i];
    for( int i = 0 ; i < n ; i++ ) cin >> b[i];
    reverse( b, b + n );

    l = -1;
    for( int i = 0 ; i < n ; i++ ){
        if( a[i] == b[i] && l == -1 ){
            l = i;
            r = i;
            flag = a[i];
        }else if( a[i] == b[i] && l != 0 ){
            r = i;
        }
    }

    if( l != -1 ){
        len = r - l, cnt = 0;
        for( int i = 0 ; i < n ; i++ ){
            if( cnt > len ) break;
            if( a[i] != flag && b[i] != flag ){
                b[cnt+l] = b[i];
                b[i] = flag;
                cnt++;
            }
        }
    }

    if( l == -1 || cnt > len ){
        cout << "Yes\n";
        for( int i = 0 ; i < n ; i++ ) cout << b[i] << " \n"[i==n-1];
    }else cout << "No\n";
}