因为$B_i$与$B_{i-1}$相邻,所以对方案数的改变最多+1.
#include<cstdio> typedef long long ll; template<class T> inline void read(T&x) { x=0;bool f=0;char c=getchar(); while((c<‘0‘||c>‘9‘)&&c!=‘-‘)c=getchar(); if(c==‘-‘)f=1,c=getchar(); while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘;c=getchar();} x=f?-x:x; } const int MAXN(200010); int B[MAXN],D[MAXN],n,D_num[MAXN],l,r,B_num[MAXN]; bool bf[MAXN];double Ans; int main() { freopen("C.in","r",stdin); freopen("C.out","w",stdout); scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%d",&D[i]); for(int i=1;i<=n;i++)scanf("%d",&B[i]),B_num[B[i]]=i; for(int i=1;i<=n;i++)D[i]=B_num[D[i]],D_num[D[i]]=i; Ans=2;bf[D_num[1]]=bf[D_num[2]]==1;l=2;r=n+1; for(int i=3;i<=n;i++) { if(D_num[i-1]>D_num[i])Ans+=1; else if(D_num[i-1]==D_num[i]-1&&n-r+1+l==i-1) { Ans+=0.5; } bf[D_num[i]]=1; while(bf[l+1])l++; while(bf[r-1])r--; } printf("%.3lf",Ans); return 0; }
原文:http://www.cnblogs.com/Oncle-Ha/p/6935171.html