ouuan 的博客

ouuan 的博客

题解 CF1172A 【Nauuo and Cards】

posted on 2019-06-08 13:49:08 | under 题解 |

首先尝试不打空白牌能否直接完成。如果能就是最优解,否则最优解一定是先打若干空白牌然后再也不打空白牌。计 $p_i$ 为 $i$ 在牌堆的初始位置(初始在手上为 $0$ ),那么答案为 $\max\limits_{i = 1}^n(p_i - i + 1 + n)$ (每张牌最早在第 $p_i + 1$ 张被打出,还要打 $n-i$ 张)。

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 200010;

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

int main()
{
    int i, j;

    scanf("%d", &n);

    for (i = 1; i <= n; ++i)
    {
        scanf("%d", a + i);
        p[a[i]] = 0;
    }

    for (i = 1; i <= n; ++i)
    {
        scanf("%d", b + i);
        p[b[i]] = i;
    }

    if (p[1])
    {
        for (i = 2; p[i] == p[1] + i - 1; ++i);
        if (p[i - 1] == n)
        {
            for (j = i; j <= n && p[j] <= j - i; ++j);
            if (j > n)
            {
                printf("%d", n - i + 1);
                return 0;
            }
        }
    }

    for (i = 1; i <= n; ++i) ans = max(ans, p[i] - i + 1 + n);

    printf("%d", ans);

    return 0;
}