Codeforces #564 (Div. 2) C. Nauuo and Cards[贪心]

题目链接:http://codeforces.com/contest/1173/problem/C

解题思路:

很明显总的抽卡次数是不会超过2*n的。然后我们再将情况分成两种:

1.编号1的卡片已经在里面了，并且最底部已经形成了一个1~x的连续的卡片，而且之后x+1,x+2都可以来得及补上，在这种情况下抽卡次数肯定就不会超过n了。

2.编号为1的卡片只能从外面重新再进来，这个时候很明显答案至少是n。然后我们再要判断最少要从顶部收取多少张卡片，我们假设一个编号为x的卡片现在在从上往下数的第i个位置，那么在1~x-1都能及时补上的情况下，x能及时补上必须要抽掉max(i-x+1,0)张顶部卡片，所以最后将这些答案取一个max就好了。

#include <bits/stdc++.h>
using namespace std;
const int mx = 2e5 + 10;
int n,p[mx],b[mx];
int main(){
	scanf("%d",&n);
	int u;
	for(int i=1;i<=n;i++) scanf("%d",&u);
	for(int i=1;i<=n;i++){
		scanf("%d",b+i);
		p[b[i]] = i;
	} 
	if(p[1]){
		int i = p[1],j;
		for(j=1;j+i<=n;j++)
		if(b[j+i]!=j+1) break;
		if(j+i==n+1){
			for(i=j+1;i<=n&&p[i]<i-j;i++);
			if(i==n+1) return 0*printf("%d\n",p[1]-1);
		}
	}
	int ans = 0;
	for(int i=1;i<=n;i++) ans = max(ans,p[i]-(i-1));
	printf("%d\n",ans+n);
	return 0;
}