題目資訊

小張在玩一種卡牌游戲，牌組由 2n 張牌組成，其中 n 張上寫有數字 1…n 各一張，其余 n 張上全部是數字 0 ，
現在牌組經過隨機打亂后，小張拿走其中 n 張牌作為手牌，其余 n 張牌作為牌堆，
小張想經過若干次如下操作使得牌堆自頂向下的牌依次為 1…n ，
每一次操作，小張選擇任意一張手牌放到牌堆底，并將牌堆頂的牌放入手牌，
他想知道最少進行幾次操作，使得牌堆自頂向下的牌依次為 1…n ，

輸入

第一行一個數 n (1 ≤ n ≤ 200000 ) ，
第二行 n 個數，表示小張手中的牌，
第三行 n 個數，表示牌堆，陣列從左向右的順序表示牌堆自頂向下的順序，

輸出

一個整數，表示最少執行的運算元，

測驗樣例

測驗樣例1

3
0 2 0
3 0 1

1

測驗樣例2

3
0 2 0
1 0 3

4

解答

#include <iostream>
#include <stdio.h>
#include <algorithm>

#define MAXN 200010

using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    //freopen("E://test.txt", "r", stdin);
    long n;
    cin >> n;

    long Hand[MAXN];//手牌
    long Desk[MAXN];//桌子上的牌

    long JiPaiQi[MAXN] = {0};//記牌器用于記錄還需要多少步才能被取出來
    long Cha[MAXN] = {0};//差值用于計算該牌
    for (int i = 0; i < n; i++)
    {
        cin >> Hand[i];
    }

    long firstdes = -1;//數字為1的具體位置
    long BigCha = 0;

    for (long i = 0; i < n; i++)
    {//此處的Desk[i]代表該牌的值
        cin >> Desk[i];
        if (Desk[i] != 0)
        {
            JiPaiQi[Desk[i]] = i + 2;//記錄著幾號牌距離能被使用還有幾步
            Cha[Desk[i]] = i + 2 - Desk[i];
            //步數減去當前牌號是一個差值，假設1號牌在0號位置，那么需要2步才能取出來
            //則最終的步數會是2-1再加上完整的一輪，是為了尋找啟動點而設計的
            if (i + 2 - Desk[i] >= BigCha)
            {
                BigCha = i + 2 - Desk[i];
            }
        }
        if (Desk[i] == 1)
        {
            firstdes = i;
        }
    }

    if (firstdes == -1)
    {//1在手里，要么是從啟動點開始，要么是直接輪著放下去就好了
        int flag = 0;
        long QiDongDian = 0;
        long bushu = Cha[1]+n;
        for (long i = 2; i <= n; i++)
        {//對所有的地下的牌進行遍歷，如果出現無法及時取出的牌則從該啟動點開始
            if (Cha[i] > QiDongDian)
            {
                flag = 1;
                QiDongDian = Cha[i];
                bushu = Cha[i] + n;
            }
        }


        if (flag == 0)
        {//全部可以及時的取出答案便是n
            cout << n << endl;
            return 0;
        }
        else
        {//無法及時取出的情況，從啟動點開始
            cout << bushu << endl;
            return 0;
        }
    }

    int op = 1;//判定此時1后面及其以后是否緊跟著2，3等
    for (long i = 0; i < n - firstdes; i++)
    {
        if (Desk[i + firstdes] != i + 1)
        {
            op = 0;
            break;
        }
    }

    if (op == 0)
    {//后方未進行緊跟
        //cout<<"hh";
        long QiDongDian = Cha[1];
        long bushu = Cha[1] + n;

        for (long i = 2; i <= n; i++)
        {
            if (Cha[i] > QiDongDian)
            {
                QiDongDian = Cha[i];
                bushu = Cha[i] + n;
            }
        }
        /*for (int i = 1; i <= n; i++)
        {
            cout << Cha[i] << " " << JiPaiQi[i] << endl;
        }*/
        cout << bushu << endl;
        return 0;
    }
    else
    {//后方緊跟的情況，需要判定是否能取到所有的數字
        //cout<<"OK"<<endl;
        int flag = 0;
        //long QiDongDian = JiPaiQi[1];
        long QiBuShuZi = n - firstdes + 1;


        for (long i = QiBuShuZi, j = 1; i <= n; i++, j++)
        {//對所有的地下的牌進行遍歷，如果出現無法及時取出的牌則從該啟動點開始
            if (JiPaiQi[i] > j)
            {
                flag = 1;
                //QiDongDian = JiPaiQi[i];
            }
        }


        if (flag == 0)
        {//全部可以及時的取出答案便是n
            cout << firstdes << endl;
            return 0;
        }
        else
        {//無法及時取出的情況，從啟動點開始
            cout << firstdes + n + 1 << endl;
            return 0;
        }
    }

}