题解 CF1172A 【Nauuo and Cards】
StudyingFather
2019-06-08 02:30:34
**Unofficial Solution to this contest also available in [Studying Father's Blog](https://studyingfather.com/archives/1304).**
------------
分两种情况考虑：
如果不用将牌堆中的每一张牌都抽出牌堆，显然最小操作数为牌堆每张牌上的数字和它的目标位置差值的最大值。
否则，牌堆中的每张牌都会被抽出一次，我们需要算出牌堆中的每张牌被抽出花费的时间和每张牌从手牌放到对应位置需要的时间。答案就是每张牌这两部分时间和的最大值。
问题就剩下如何判断当前局面对应哪一种情况。
考虑编号为 $ 1 $ 的牌，如果它刚开始在手牌里，显然剩下的牌都需要被抽出一次。
否则，我们需要计算在 $ 1 $ 号牌被抽出前，剩下所有的牌是否都能到达预定位置，且当前牌堆中任意一张牌与 $ 1 $ 号牌的相对位置差与最终局面的相对位置差是否相等。如果相对位置差完全相等，或是无需抽出 $ 1 $ 号牌即可让剩下的牌都能到预定位置，就按第一种情况处理即可。
```cpp
#include <cstdio>
#include <algorithm>
using namespace std;
int a[200005],b[200005],res1[200005],res2[200005],pos[200005],n;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
res1[i]=n-i+1;
}
for(int i=1;i<=n;i++)
{
scanf("%d",&b[i]);
res2[b[i]]=i;
pos[b[i]]=i;
}
int flag=1;
for(int i=2;i<=n;i++)
if(res2[1]<=res1[i]+res2[i]&&pos[i]-pos[1]!=i-1)
{
flag=0;
break;
}
if(pos[1]==0)flag=0;
if(!flag)
{
int ans=0;
for(int i=1;i<=n;i++)
ans=max(ans,res1[i]+res2[i]);
printf("%d\n",ans);
}
else
{
int ans=0;
for(int i=1;i<=n;i++)
if(i>b[i])ans=max(ans,i-b[i]);
printf("%d\n",ans);
}
return 0;
}
```