题解 P1966 火柴排队

题面

两个数列 \(a,b\)，求最少相邻两数交换多少次使得 \(\sum_{i=1}^n{(a_i-b_i)^2}\) 最小

思路

先来简单地变换一下式子（见到这种狗式子一定要拆）： \[ \sum{(a_i-b_i)^2}=\sum(a_i^2+b_i^2-2a_ib_i) \] \(\sum(a_i^2+b_i^2)\) 是不变的，所以要最大化 \(\sum{a_ib_i}\)

所以要让 \(a,b\) 中排名第 k 的两个数在同一位置上

为啥？一点也不严谨的口胡证明：

假设有四个数 \(x_1,x_2,y_1,y_2\)，且 \(x_1<x_2,y_1<y_2\)

那么 \(x_1y_1+x_2y_2>x_1y_2+x_2y_1\)，这很显然吧

也就是说 \(a,b\) 中最大两数乘积、次大两数乘积……的和是最大的

然后怎么做？

让排名为 k 的 \(a_i,b_j\) 两数在同一位置上，就是让 \(b_j\) 到位置 \(i\) 上

令 \(b_j=i\)，再将 \(b\) 数组排序，\(b_j\) 自然到位置 \(i\) 上了

是相邻两数交换来排序的话，最少次数就是此时 \(b\) 的逆序对数（挺好证吧）

直接上树状数组或者归并

code

出题人还算良心，同一数列中两两各不相同，少了许多细节

评测记录

#include <cstdio>
#include <cctype>
#include <algorithm>

using namespace std;

template<typename T> inline void read(T &x) {/* fast read */}

const int N = 1e5 + 9;
const int MOD = 99999997;

int n, ans;
int a[N], b[N], tmp[N];

// 离散化
inline void lsh(int *t) {
    for (int i = 1; i <= n; ++i) tmp[i] = t[i];
    sort(tmp+1, tmp+n+1);
    int tot = unique(tmp+1, tmp+n+1) - tmp;
    for (int i = 1; i <= n; ++i)
        t[i] = lower_bound(tmp+1, tmp+tot+1, t[i]) - tmp;
}

// 树状数组，用于求逆序对
struct Bit_Tree {
    int tr[N];
    #define lowbit(x) (x & -x)
    inline void add(int x, int k) {
        while (x <= n) 
            tr[x] += k, x += lowbit(x);
    }
    inline int query(int x) {
        int re = 0;
        while (x) 
            re += tr[x], x -= lowbit(x);
        return re;
    }
} tr;

inline void main() {
    read(n);
    for (int i = 1; i <= n; ++i) read(a[i]);
    for (int i = 1; i <= n; ++i) read(b[i]);
    // 离散化，同时也是得到每个数的排名
    lsh(a), lsh(b);
    // 让 b 数列每个元素得到 a 中同一排名元素的坐标
    for (int i = 1; i <= n; ++i)
        tmp[a[i]] = i;
    for (int i = 1; i <= n; ++i)
        b[i] = tmp[b[i]];
    // 统计答案
    for (int i = 1; i <= n; ++i) {
        // 每次加入一个数增加逆序对数：原个数 - 小于它的元素个数
        ans = (ans + i - 1 - tr.query(b[i])) % MOD;
        tr.add(b[i], 1);
    }
    printf("%d\n", ans);
}