NOIP的题就是好.

题面:P1966 [NOIP2013]火柴排队

分析

如果问我需要多少次交换能把一个序列排好序,我就可以直接用归并排序求逆序对.但是本题不走寻常路.我们先来分析一下题目.

题目要求$\sum_{i=1}^{n}(a_i-b_i)^2$最小.我们应该把什么样的局面作为目标呢?类似于邻项交换类的贪心问题,假设我们有$a_1,a_2,b_1,b_2$这两个数组.其中$a_1< a_2,b_1< b_2$.现在我们有两种选择:

  1. 把$a_1$和$b_1$配对,那么两列火柴的距离就是$(a_1^2+b_1^2+a_2^2+b_2^2)-2(a_1b_1+a_2b_2)$
  2. 把$a_1$和$b_2$配对,那么两列火柴的距离就是$(a_1^2+b_1^2+a_2^2+b_2^2)-2(a_1b_2+a_2b_1)$

两式相减,不考虑常数,我们得到$-(a_1b_1+a_2b_2)+(a_1b_2+a_2b_1)$如果第二种选择比第一种选择得到的距离要更小,就意味着
$$
a_1b_2+a_2b_1>a_1b_1+a_2b_2\
\Rightarrow a_1(b_2-b_1)>a_2(b_2-b_1)\
\Rightarrow a_1> a_2
$$
这不就矛盾了吗?所以假设不成立.那么只有把$a$种第$i$小的和$b$中第$i$小的排在相同的位置才行.换句话说,我们就要通过交换使得离散化后的$a_i=b_i$.当然了,离散化只是为了体现出排名,我们也可以进行其他的操作来达到相同的目的.

比如,我们设有一个函数$q()$,这个函数的功能是这样的:如果输入原$a$数列中第$i$小的数的位置,它就会返回原$b$数列中第$i$小的数的位置.这样就把两个应该相等化的值联系起来了.然后我们发现由于原序列已经给定,我们可以预处理出$q()$函数的可能的值,使得它变成$q[]$数组.具体怎么做呢?

我们用结构体的形式来储存两列火柴,结构体保存每根火柴的高度和在原序列中的下标.然后按照高度从小到大排序.这样得到的下标序列$a[i].ind$的意义就是原序列中第$i$小的数所在的位置.对b做同样的处理后,我们的$q$数组该怎么处理就显而易见了.输入$a[i].ind$返回$b[i].ind$,也就是$q[a[i].ind]=b[i].ind$.

如果我们通过交换来修改原序列,那么$a[i].ind$的值就会发生变化,$q$的值也会发生变化.我们最终的目的是$a[i].ind=b[i].ind$,那么就有$q[a[i].ind]=a[i].ind$即$q[k]=k(k=a[i].ind)$.这样一看,不就是让$q[1]=1,q[2]=2…$,把$q$排好序吗?而我们只能交换相邻项,所以求出$q$的逆序对个数就是答案了.

代码:

#include <cmath>
#include <queue>
#include <deque>
#include <cctype>
#include <string>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define mod 9999997
#define int long long
using namespace std;

template<class T> inline void read(T &x) {
    x = 0;
    char ch = getchar(), w = 0;
    while (!isdigit(ch)) w = (ch == '+'), ch = getchar();
    while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
    x = w ? x : x;
    return;
}

int n, q[100000], temp[100000], cnt;

struct node {
    int val, ind;
}a[100000], b[100000];

inline bool cmp1(node x, node y) {
    return x.val < y.val;
}

inline bool cmp2(node x, node y) {
    return x.val < y.val;
}

void merge_sort(int l, int r) {
    if (l == r) return;
    int mid = l + r >> 1;
    merge_sort(l, mid);
    merge_sort(mid + 1, r);
    int i = l, j = mid + 1, t = l;
    while (i <= mid && j <= r) {
        if (q[i] <= q[j])
            temp[t] = q[i], i++;
        else {
            temp[t] = q[j], j++;
            cnt += (mid - i + 1);
            cnt %= mod;
        }
        t++;
    }
    while (i <= mid)
        temp[t] = q[i], t++, i++;
    while (j <= r)
        temp[t] = q[j], t++, j++;
    for (int k = l; k <= r; ++k)
        q[k] = temp[k];
    return;
}

signed main() {
    read(n);
    for (int i = 1; i <= n; ++i)
        read(a[i].val), a[i].ind = i;
    for (int i = 1; i <= n; ++i)
        read(b[i].val), b[i].ind = i;
    sort(a + 1, a + 1 + n, cmp1);
    sort(b + 1, b + 1 + n, cmp2);
    for (int i = 1; i <= n; ++i)
        q[a[i].ind] = b[i].ind;
    merge_sort(1, n);
    cout << cnt << endl;
    return;
}
// 拒绝抄袭,从我做起

本题思路真是非常巧妙,尤其是$q$数组的设想,蒟蒻的我也是参考了好多题解和思路才得到了这种理解.思维的灵活性是真的重要啊.

——Gensokyo