1 second
256 megabytes
standard input
standard output
Jeff has become friends with Furik. Now these two are going to play one quite amusing game.
At the beginning of the game Jeff takes a piece of paper and writes down a permutation consisting of n numbers: p1, p2, ..., pn. Then the guys take turns to make moves, Jeff moves first. During his move, Jeff chooses two adjacent permutation elements and then the boy swaps them. During his move, Furic tosses a coin and if the coin shows "heads" he chooses a random pair of adjacent elements with indexes i and i + 1, for which an inequality pi > pi + 1 holds, and swaps them. But if the coin shows "tails", Furik chooses a random pair of adjacent elements with indexes i and i + 1, for which the inequality pi < pi + 1 holds, and swaps them. If the coin shows "heads" or "tails" and Furik has multiple ways of adjacent pairs to take, then he uniformly takes one of the pairs. If Furik doesn't have any pair to take, he tosses a coin one more time. The game ends when the permutation is sorted in the increasing order.
Jeff wants the game to finish as quickly as possible (that is, he wants both players to make as few moves as possible). Help Jeff find the minimum mathematical expectation of the number of moves in the game if he moves optimally well.
You can consider that the coin shows the heads (or tails) with the probability of 50 percent.
The first line contains integer n (1 ≤ n ≤ 3000). The next line contains n distinct integers p1, p2, ..., pn (1 ≤ pi ≤ n) — the permutation p. The numbers are separated by spaces.
In a single line print a single real value — the answer to the problem. The answer will be considered correct if the absolute or relative error doesn't exceed 10 - 6.
2
1 2
0.000000
5
3 5 2 4 1
13.000000
In the first test the sequence is already sorted, so the answer is 0.
题意：两个人玩游戏，给n个数，第一个人选取相邻两个递减的数交换顺序，第二个人一半的概率选取相邻两个递减的数交换顺序，一半的概率选取相邻两个递增的数交换顺序。两个人轮流操作，求整个数列变成递增数列所需交换次数的期望。
思路：我们知道，一个序列中， a[i] > a[j]这样的数对称为逆序数对，而题目的意思其实就是求把数列中的逆序对的数量变成0时所要的最小步数，于是可以这么做，求出逆序对的数量，然后算出递推公式，找规律，算到最后发现是两个等差数列。。。以下是递推过程：
假设d[i]为当逆序对为i对时所需要的步数，那么d[0]=0,d[1]=1,这是已知的，当i>=2，d[i]=0.5*d[i-1-1]+0.5*d[i-1+1]+1+1,化简得d[i]=d[i-2]+4;
所以，d[0]=0,d[2]=4,d[4]=8,d[6]=12;
d[1]=1,d[3]=5,d[5]=9,d[7]=13;
所以，当i为偶数时，d[i]=i*2;
当i为奇数时，d[i]=i/2*4+1;
#include<bits/stdc++.h>
using namespace std;
int main() {
int n, cnt = ;
double a[];
cin >> n;
for(int i = ; i < n; i++)
cin >> a[i];
for(int i = ; i < n; i++) {
for(int j = i + ; j < n; j++) {
if(a[i] > a[j])
cnt++;//逆序对个数
}
}
if(cnt % == )
printf("%f\n", (cnt * ));
else
printf("%f\n", (cnt / * + ));
return ; }