Codeforces 1172A Nauuo and Cards

题目链接：http://codeforces.com/problemset/problem/1172/A

题意：一共有2*n张牌，n张0，n张1到n。现在随机的n张(有0有数字)在手上，另n张再牌堆中，现在已知手上的牌和牌堆的牌，可以进行多次以下操作：将手中任意一张牌放入牌堆底，将牌堆顶的一张牌放入手中。问最少多少次后可使牌堆顶到牌堆底的n张牌分别为1,2,3...n。

思路：模拟，判断现有牌堆底能不能继续往下接，例如00123456.不能的话还是等1取出来再往下放。

AC代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5+5;
int vis[maxn];
int a[maxn];
int b[maxn];
int n;
bool check(int b[])
{
    int i;
    bool flag = true;
    for(i = 0;i < n;i++)
    {
        if(b[i] == 1) break;
    }
    if(i == n) return false;
    for(i = i + 1;i < n;i++)
    {
        if(b[i] != b[i-1] + 1) flag = false;
    }
    return flag;
}
int main()
{
    int *it = b;
    int t = 1;
    int ans = 0;
    bool flag = false;
    cin >> n;
    for(int i = 0;i < n;i++) cin >> a[i],vis[ a[i] ] = 1;
    for(int i = 0;i < n;i++) cin >> b[i];
    if(check(b)) t = b[n-1] + 1,flag = true;
    while(t <= n)
    {
        if(!flag)
        {
            if(vis[t])
                t++;
            ans++;
            vis[*it]++;
            it++;
        }
        else{
            if(vis[t])
                t++;
            else
            {
                ans = 0;
                t = 1;
                it = b;
                for(int i = 0;i < n;i++) vis[i] = 0;
                for(int i = 0;i < n;i++) vis[ a[i] ] = 1;
                flag = false;
                continue;
            }
            ans++;
            vis[*it]++;
            it++;
        }
 
    }
    cout << ans;
    return 0;
}

Codeforces 1172A Nauuo and Cards

相关推荐