P1966 [NOIP 2013 提高组] 火柴排队

· · 算法·理论

题意：

已知有两盒n根的小火柴，分别摆成两排，问要是两排小火柴处于同一位置的小火柴a_i,b_i的距离最小需要几次交换 （距离为(a_i-b_i)^2,a_i为第一排第i根小火柴的高度，b_i为第二排第i根小火柴的高度）

思路：

既然我们需要求 \sum (a_i-b_i)^2 最小时改变数组需要的最小步数，那么我们就需要知道怎样排列下 \sum (a_i-b_i)^2 最小

(a_i-b_i)^2={a_i}^2+{b_i}^2-2\times a_i\times b_i

因为有 \sum 的存在所以公式中{a_i}^2与 {b_i}^2时相对独立的，与排列的顺序无关，而 a_i\times b_i 才对排列的顺序有关

举个例子：

a={1,2}\\ b={3,4}

当a固定时b可以为[3,4]或[4,3]

当b为[3,4]时

\sum (a_i-b_i)^2=1^2+2^2+3^2+4^2-2\times 1\times 3-2\times2\times 4

而当b为[4,3]

\sum (a_i-b_i)^2=1^2+2^2+3^2+4^2-2\times1\times 4-2\times2\times 3

可以看出 \sum (a_i-b_i)^2 中无论如何排列 {a_i}^2+{b_i}^2 一定存在且相等，而2\times a_i\times b_i 会因顺序不同而影响答案

而在计算时需要减去 2\times a_i\times b_i ，所以 a_i\times b_i 越大 \sum (a_i-b_i)^2 越小，又知道当两数相乘时两数越相近乘机就越大，那么如何使每对{a_i}与 {b_i}相对接近呢？其实使第一排与第二排的小火柴顺序排列就可以使每对{a_i}与 {b_i}相对接近

而我们可以发现交换第一排的火柴顺序与交换第二排的火柴顺序的代价相等，所以我们可以固定第一排的顺序，仅计算第二排要使其与第一排的大小相对顺序相等的最小代价即可

而我们发现当第一排顺序排列时要求出第二排交换的次数其实就是求当第二排对于第一排相对顺序排列时再次使用冒泡排序时的交换数量，而冒泡排序的交换数量就是求逆序对的数量，所以我们只需要用树状数组或归并排序求逆序对的数量就行了

代码

树状数组：

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e5 + 7;
const int mod = 1e8 - 3;
int n, c[maxn], t[maxn], ans; // c[i]：a[i]代表的最终位置
struct Node
{
    int id, v;
} a[maxn], b[maxn];
bool cmp(Node a, Node b)
{
    return a.v < b.v;
}
int lowbit(int x)
{
    return x & -x;
}
void modify(int x, int v)
{
    while (x <= n)
    {
        t[x] += v;
        x += lowbit(x);
    }
}
int query(int x)
{
    int sum = 0;
    while (x > 0)
    {
        sum += t[x];
        x -= lowbit(x);
    }
    return sum;
}
signed main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i].v, a[i].id = i;
    }
    for (int i = 1; i <= n; i++)
    {
        cin >> b[i].v, b[i].id = i;
    }
    sort(a + 1, a + 1 + n, cmp);
    sort(b + 1, b + 1 + n, cmp);
    for (int i = 1; i <= n; i++)
    {
        c[b[i].id] = a[i].id;
    }
    for (int i = n; i; i--)
    {
        ans += query(c[i]);
        modify(c[i], 1);
    }
    cout << ans % mod << "\n";
    return 0;
}

归并排序：

#include<bits/stdc++.h>
using namespace std;
int n;
int x[10000010];
int mod=1e8-3;
struct node{
    int id;
    int s;
}a[100010],b[100010];
int y[100010];
long long ans=0;
bool cmp(node a,node b){
    return a.s<b.s;
}
void gb_sort(int l,int r){
    if(l==r){
        return;
    }
    int mid=(l+r)/2;
    gb_sort(l,mid);
    gb_sort(mid+1,r);
    int i=l,j=mid+1;
    int k=l;
    while(i<=mid&&j<=r){
        if(x[i]<=x[j]){
            y[k++]=x[i++];
        }else{
            ans=(ans+mid-i+1)%mod;
            y[k++]=x[j++];
        }
    }
    while(i<=mid){
        y[k++]=x[i++];
    }
    while(j<=r){
        y[k++]=x[j++];
    }
    for(int o=l;o<=r;o++){
        x[o]=y[o];
    }
    return;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i].s;
        a[i].id=i;
    }
    for(int i=1;i<=n;i++){
        cin>>b[i].s;
        b[i].id=i;
    }
    sort(a+1,a+n+1,cmp);
    sort(b+1,b+n+1,cmp);
    for(int i=1;i<=n;i++){
        x[b[i].id]=a[i].id;
    }
    gb_sort(1,n);
    cout<<ans<<"\n";
    return 0;
}

注意点：需要对10^8+3取余 80分 and 不开 long long 90分