这个题不错…纪念一下

懵逼的 题目

传送至 Vijos

扯淡的 题解

一开始和很多人想的一样:

  • 使用一个结构体包含两个变量A, B
  • 按照先A, 后B的顺序排序
  • 在B中找逆序对

但是错了

需要注意的是调换顺序不是在排完序的序列里调换的, 而是在原序列中调换的!
辣鸡样例居然能过
所以我们需要的是让B数组和A数组在原序列中一一对应起来, 而非在排完序的序列中再操作
想明白这个这个题就比较简单了:

  • 先在原序列中记录A数组中每个数的位置
  • 然后给A, B分别排序, 找到A与B之间每个元素的对应关系
  • 然后把B恢复原状, 把Bi替换成 [ 排序后的序列中与Bi对应的Ai 在原序列中的编号]
  • 求逆序对
    结束, AC

还有就是为什么两个序列对应的时候费用最小:

  • (a - b) ^ 2 = a ^ 2 - 2ab + b ^ 2
  • sigma a ^ 2 + b ^ 2 肯定不变, 因为序列的元素没变
  • 所以当 -2ab 最小的时候, sigma (a - b) ^ 2 最小
  • 根据正方形面积大于周长相等长方形的面积, 当 a 与 b 接近时, ab最大, -2ab最小
    结束, 得证

沙茶的 代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define MAXN (100000 + 5)
#define MOD (99999997)
using namespace std;
struct xl
{
    int a;
    int bh;
}ma[MAXN], mb[MAXN];
int n;
int ans;
int b[MAXN];
int t[MAXN];
void init();
//void mmerge(int, int);
void work(int, int);
bool cmp(xl, xl);
void solve();
int main()
{
    init();
    solve();
    printf("%d", ans);
    return 0;
}
void init()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &ma[i].a);
        ma[i].bh = i;
    }
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &mb[i].a);
        mb[i].bh = i;
    }
}
void solve()
{
    sort(ma + 1, ma + n + 1, cmp);
    sort(mb + 1, mb + n + 1, cmp);
    for (int i = 1; i <= n; i++)
    {
        b[mb[i].bh] = ma[i].bh;
    }
    work(1, n);
}
void work(int le, int ri)
{
    if (le < ri)
    {
        int mi = (le + ri) >> 1;
        work(le, mi);
        work(mi + 1, ri);
        int i = le, j = le, k = mi + 1;
        while(i <= ri && j <= mi && k <= ri)
        {
            if (b[j] > b[k])
            {
                ans += mi - j + 1;
                ans %= MOD;
                t[i++] = b[k++];
            }
            else
            {
                t[i++] = b[j++];
            }
        }
        for (; j <= mi; j++)
        {
            t[i++] = b[j];
        }
        for (; k <= ri; k++)
        {
            t[i++] = b[k];
        }
        for (int z = le; z <= ri; z++)
        {
            b[z] = t[z];
        }
    }
}
bool cmp(xl x, xl y)
{
    if (x.a == y.a)
    {
        return x.bh < y.bh;
    }
    else
    {
        return x.a < y.a;
    }
}

/*
4
2 3 1 4
3 2 1 4


1
*/

By 因为没写作业站了一节课神清气爽的 Cansult