【归并排序】奶牛的图片（jzoj 1812）

奶牛的图片

jzoj 1812

题目大意

给你一个序列，你可以交换相邻的两个数
让你用最少的交换次数来使得这个序列变成形如$a+1,a+2...n,1,2...a-1,a$a+1,a+2...n,1,2...a−1,a的序列
问你最少的交换次数是多少次

输入样例

5
3
5
4
2
1

输出样例

2

解题思路

如果我们变成$1,2...n$1,2...n所需次数就是他的逆序对（证明上网找）
如果我们把1放到n后面，那逆序对就要减去1原来的贡献再加上1现在的贡献
就是$-(s_i - 1)+(n-s_i)$−(si​−1)+(n−si​),然后枚举每一种情况，求最小解
注：$s_i$si​是指$i$i的初始位置

代码

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
ll n, g, ans, a[100010], b[100010], s[100010];
void work(ll l, ll r)//归并排序求逆序对
{
	if (l >= r) return;
	ll mid = (l + r) / 2;
	ll L = l, R = mid + 1;
	work(l, mid);
	work(mid + 1, r);
	for (ll i = l; i <= r; ++i)
	{
		if ((a[L] < a[R] || R > r) && L <= mid) b[i] = a[L++];
		else 
		{
			b[i] = a[R++];
			g += mid - L + 1;
		}
	}
	for (ll i = l; i <= r; ++i)
		a[i] = b[i];
	return;
}
int main()
{
	scanf("%lld", &n);
	for (ll i = 1; i <= n; ++i)
	{
		scanf("%lld", &a[i]); 
		s[a[i]] = i;
	}
	work(1, n);
	ans = g;
	for (ll i = 1; i < n; ++i)
	{
		g = g - (s[i] - 1) + (n - s[i]);//把当前的第一个数放到最后
		ans = min(ans, g); 
	}
	printf("%lld", ans);
	return 0;
}