感觉这个题思路很有趣的w
这是题解w：http://www.cnblogs.com/IcyF/p/4641564.html
1 #include2 #include 3 #include 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\n", ans + 0.999);42 printf("%.3f\n", ans + 1.000);43 printf("%.3f\n", 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 }