感觉这个题思路很有趣的w
这是题解w：http://www.cnblogs.com/IcyF/p/4641564.html
1 #include <cstdio> 2 #include <cstdlib> 3 #include <iostream> 4 #define MaxN 200010 5 using namespace std; 6 int n; 7 int d[MaxN], b[MaxN], map[MaxN], s[MaxN], da[MaxN], fl[MaxN], pos[MaxN]; 8 9 void read(int &a){ 10 a = 0; char c = getchar(); 11 while (c < '0' || c > '9') c = getchar(); 12 while (c >= '0' && c <= '9' ) a = a*10 + c-'0', c = getchar(); 13 } 14 15 void Read_Data(){ 16 read(n); 17 for (int i = 1; i <= n; i++) read(d[i]); 18 for (int i = 1; i <= n; i++) read(b[i]), map[b[i]] = i; 19 for (int i = 1; i <= n; i++) d[i] = map[d[i]]; 20 for (int i = 1; i <= n; i++) pos[d[i]] = i; 21 } 22 23 void Solve(){ 24 da[1] = 1 , s[1] = 1, ++fl[1], --fl[2]; 25 for (int i = 1; i < n; i++) { 26 if (pos[i] > pos[i+1]) da[i] = 1, ++fl[i], --fl[i+1]; 27 s[i] = s[i-1]+da[i]; 28 } 29 for (int i = 1; i < n; i++) { 30 if (d[i] > d[i+1]) continue; 31 int t = s[d[i+1]-1] - s[d[i]-1]; 32 if (t) ++fl[d[i]], --fl[d[i+1]]; 33 } 34 int flag = 0; 35 double ans = 0.0; 36 for (int i = 1; i < n; i++) { 37 flag += fl[i]; 38 if (flag) ans += (double) da[i]; 39 else ans += 0.5; 40 } 41 printf("%.3f ", ans + 0.999); 42 printf("%.3f ", ans + 1.000); 43 printf("%.3f ", ans + 1.001); 44 } 45 46 int main() 47 { 48 freopen("count.in", "r", stdin); 49 freopen("count.out", "w", stdout); 50 Read_Data(); 51 Solve(); 52 fclose(stdin); 53 fclose(stdout); 54 return 0; 55 }