P1966 [NOIP 2013 提高组] 火柴排队 - 洛谷
分析
-
求∑(ai−bi)2取最小值等价于∑aibi取到最大值，根据排序不等式，当{ai}与{bi}的序相同时，∑aibi取到最大值
-
将ai和bi分别映射为序，即ai在原数列中第k大，则ai->k
-
每次操作交换相邻的元素，交换一次ai a(i-1) 等价于 交换一次bi b(i-1)，于是我们只考虑对一边进行操作
-
将bi映射为 i ,然后以相同映射法则对ai映射，问题转化为{ai}操作几次变为升序
-
{ai}升序等价于{ai}中没有逆序对，容易归纳证明，操作次数={ai}中逆序对数，逆序对数用归并排序即可
代码
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define mid ((l+r)>>1)
using namespace std;
const int N = 1e6+10;
const int mod = 1e8-3;struct num
{int val;int ord;
} a[N], b[N];bool cmp(num x, num y)
{return x.val < y.val;
}int cnt = 0;
int c[N], d[N], e[N], f[N];void solve(int l, int r)
{if (l >= r) return ;solve(l, mid), solve(mid + 1, r);for (int i = l, j = l, k = mid + 1; i <= r; i++){if ( j <= mid and k <= r){if (c[j] > c[k] ) e[i] = c[k++], cnt += mid - j + 1,cnt%=mod;else e[i] = c[j++];}else{if (j == mid + 1)e[i] = c[k++];elsee[i] = c[j++];}}for (int i = l; i <= r; i++)c[i] = e[i];
}
signed main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int n;cin >> n;for (int i = 1; i <= n; i++)cin >> a[i].val, a[i].ord = i;for (int i = 1; i <= n; i++)cin >> b[i].val, b[i].ord = i;sort(a + 1, a + 1 + n, cmp);sort(b + 1, b + 1 + n, cmp);for (int i = 1; i <= n; i++)c[a[i].ord] = i, d[b[i].ord] = i;for (int i = 1; i <= n; i++)f[d[i]] = i;for (int i = 1; i <= n; i++)c[i] = f[c[i]];
// for (int i = 1; i <= n; i++)
// cout << c[i] << " ";solve(1ll, n);cout << cnt;return 0;
}