P1966 火柴排队

传送门

思路

转化距离定义可知目标是求 Σ(ai*bi) 的最大值，这要求 a 列和 b 列以大小比较为相对顺序的序列完全相等。那么首先要得到两列的以大小比较为相对顺序的序列，一提到相对顺序就需要联想到离散化。离散化后，由于两个序列都是一个n的全排列，可以先把 ai 映射作 i ，a列转化为1到n的顺序排列，并对 b列也作相同映射。将b列转化为a列的最小步骤的实质是求解映射后的 b列中的逆序对（每一次交换，最多可以让序列中的逆序对减一，当序列中没有逆序对时，则b=a，那么最小操作数则为逆序对个数）。用归并排序求解b列的逆序对个数。

代码

#include
#include
#include
#define mod 99999997
#define maxn 100007
using namespace std;
int a[maxn], b[maxn], n, ans, t[maxn], lsa[maxn], lsb[maxn];
mapMap;
void merge_sort(int arr[], int l, int r)
{
    if (l == r) return;
    int mid = (l + r) >> 1;
    merge_sort(arr, l, mid), merge_sort(arr, mid + 1, r);
    for (int i = l, j = l, k = mid + 1; i <= r; i++)
    {
        if (j == mid + 1) t[i] = arr[k++];
        else if (k == r + 1) {
            t[i] = arr[j++];
            ans += k - mid - 1;
            ans %= mod;
        }
        else if (arr[j] < arr[k]) {
            t[i] = arr[j++];
            ans += k - mid - 1;
            ans %= mod;
        }
        else t[i] = arr[k++];
    }
    for (int i = l; i <= r; i++)
        arr[i] = t[i];
}
int main(void)
{
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i], lsa[i] = a[i];
    for (int j = 1; j <= n; j++)
        cin >> b[j], lsb[j] = b[j];
    sort(lsa + 1, lsa + n + 1);
    sort(lsb + 1, lsb + n + 1);
    for (int i = 1; i <= n; i++)
    {
        a[i] = lower_bound(lsa + 1, lsa + n + 1, a[i]) - lsa;
        b[i] = lower_bound(lsb + 1, lsb + n + 1, b[i]) - lsb;
        Map[a[i]] = i;
    }
    for (int i = 1; i <= n; i++)
        b[i] = Map[b[i]];
    merge_sort(b, 1, n);
    cout << ans << endl;
    return 0;
}
洛谷OJ离散化

相关

cf1190 D. Tokitsukaze and Strange Rectangle（计数、离散化、树状数组）

Ultra-QuickSort（树状数组+离散化） POJ - 2299

AcWing 4195. 线段覆盖（离散化+差分）

什么是离散化？C++实现方法

AcWing 1987.粉刷栅栏（离散化，差分）

线段树 区间离散化

洛谷P1496 火烧赤壁 （模拟/离散化+差分）

离散化学习笔记

离散化模板

算法基础课：离散化

标签