题解 CF1172A 【Nauuo and Cards】

ouuan

2019-06-08 13:49:08

Solution

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