bit 1088

車両再編
時間制限:1秒メモリ制限:10240 KB
Problem Description
旧式の駅のそばに橋があり、その橋面は川の中心の橋脚を水平に回転することができる.1つの駅の従業員は、橋の長さが最大2両の車両を収容できることを発見し、橋を180度回転すれば、隣接する2両の車両の位置を交換することができ、この方法で車両の順序を並べ直すことができる.
そこで彼はこの橋で駅に入った車両を車両番号で小さいから大きいまで並べる責任を負った.
彼が定年退職した後、駅はこの仕事を自動化することにした.その中の重要な仕事はプログラムを編んで、最初の車両の順序を入力して、少なくとも何歩で車両を並べ替えることができるかを計算することだ.
Input
入力ファイルには2行のデータがあり、1行目は車両総数N(100000以下)であり、2行目はN個の異なる数で初期の車両順序を表す.
Output
1つのデータは、最も少ない回転回数です.
Sample Input
4
4 3 2 1
Sample Output 6
直接逆序数を求めて解決して、最初はデータ型が間違っていて、直接ひざまずいて、longlongに変えて過ぎて、黒いのは惨めです.

#include <stdio.h>
long long input[100010],ans;
long long c[100010];
void merge(int begin,int end)
{

    //               
	if(begin + 1 >= end) return;

    //  
	long long mid = (begin+end)/2;
	merge(begin,mid);
	merge(mid,end);

	//  ，ans      。
	int k = 0,i = begin,j = mid;
	for(; i<mid && j<end;)
	{
		if(input[i] < input[j])
		{
			c[k ++] = input[i++];
		}else{
			c[k ++] = input[j++];
			ans += mid - i;
		}
	}
	//  [begin,mid）          C       input;
	while(i<mid)
	{
		c[k++] = input[i++];
	}
	for(i = 0;i<k;++i)
	{
		input[i+begin] = c[i];
	}
	return;
}
int main()
{
	long long N;
	//while(~scanf("%d",&N))
	//{
        scanf("%lld",&N);
		for(long long i = 0;i<N;++i)
            scanf("%lld",&input[i]);
		ans = 0;
		merge(0,N);
		printf("%lld
",ans);
	//}

	return 0;
}