SDTBU-ACM集训队暑期集训---组队赛 1

题目： A Sorting Problem

题意：

给定由n个互不相同的正整数（1~n）组成的序列，每次选择两个差的绝对值为1的整数，交换它们的位置，问最少交换几次可以使得整个数列有序。

输入格式

输入第一行是一个整数n。

第二行有n个整数。

输出格式

输出一个整数，表示最小交换次数。

数据范围

1 < n ≤ 200000

1 ≤ p[i] ≤ n

所有的p[i]都是不同的

输入样例：

5
5 3 2 1 4

输出样例：

7

思路：

• 我们可以思考这样一个问题，如何通过交换，将样例中的1放到第一位？显然如果想要将1放到第一位，那么必须先将2放到第一位，然后让2和1交换位置，同理，要将2放到第一位需要先将3放到第一位…，那么我们就会发现，将1放到第一位需要交换的次数就是 5-1 = 4 次，而交换后与第一位交换过的数都要变为比自己大1的数，为什么？因为我们将5变小到1的过程中，与第一位进行交换的数都比第一位小1。
• 容易想到的是恒有 a[i]>=i ，因为我们是从前向后遍历的每一位，所以前 i-1 位都已经放好了。
• 那么就可以得到
  • 第一步：第 i 位交换的次数就是 a[i]-i 。
  • 第二步：将第 i 位后面 [i+1, a[i]] 每个数加1。
• 因为 n 最大有 10⁵ ，直接遍历会超时~~，痛！~~。
• 如何优化？我们重新审视上面两步会发现第一步∑为0，因为数列的组成元素就是 [1, n] ，两个相同的集合相减结果显然为∅。
• 那么就只用考虑第二步，依次去找每个数后面比他小的数似乎很难，那么我们可以将问题转为求∑区间[1, i-1]小于a[i]的数量，我们会惊讶的发现，这实际上就是求整个数列的逆序对！直接套用 归并排序模板 的模板就可以。
• 虽然当时这道题做出来了，但是时间错了6次才最终看明白是在考察逆序对。顺便提醒一下模板的重要性。

代码：

直接做，TLE

#include<iostream>
#include<string>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<unordered_map>

using namespace std;

#define PII pair<int,int>
#define ll long long

const int N = 200010;

int n;
//a数组存原数列，b[i]表示i在a数组中的位置
int a[N],b[N];
ll res;

int main()
{
	cin >> n;
	for (int i = 1; i <= n; ++i)
	{
		cin >> a[i];
		b[a[i]] = i;
	}

	for (int i = 1; i <= n; ++i)
	{
		if (a[i] == i)continue;
        
        //第一步
        res += a[i] - i;
        //第二步
        int t = a[i];
        for (int j = i; j <= t; ++j)a[b[j]]++;
        //滚动数组，逆序修改b数组
        for (int j = t-1; j >=i; --j)b[j + 1] = b[j];
        a[i] = i;
	}

	cout << res;
	return 0;
}

区间合并求逆序对

#include<iostream>
#include<string>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<unordered_map>
#include<queue>

using namespace std;

#define PII pair<int,int>
#define ll long long

const int N = 200010;

int n;
int a[N],tmp[N];
ll res;

//区间合并模板
void merge_sort(int q[], int l, int r)
{
    if (l >= r) return;

    int mid = l + r >> 1;
    merge_sort(q, l, mid);
    merge_sort(q, mid + 1, r);

    int k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r)
  	    if (q[i] <= q[j]) tmp[k++] = q[i++];
        else
        {
            res += mid-i+1;
            tmp[k++] = q[j++];
        }

    while (i <= mid) tmp[k++] = q[i++];
    while (j <= r) tmp[k++] = q[j++];

    for (i = l, j = 0; i <= r; i++, j++) q[i] = tmp[j];
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; ++i)cin >>a[i];

    merge_sort(a,1,n);
    cout << res;
	return 0;
}