卡牌游戏

• 题目信息
• • 输入
  • 输出
  • 测试样例
• 解答

题目信息

小张在玩一种卡牌游戏，牌组由 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;
            }
        }
        
        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;
        }
    }

}