CF 1513F Swapping Problem

题目描述

http://codeforces.com/problemset/problem/1513/F

简要题意：给定两个长度为 $n$ 的序列 $a_i,b_i$，现在至多可以交换一次 $b$ 中两个位置的值，最小化 $\sum_{i=1}^n|a_i-b_i|$

$n\le 2\times 10^5$

Solution

我们考虑交换 $b_i$ 和 $b_j$，令 $sum=\sum_{i=1}^n |a_i-b_i|，t_i=|a_i-b_i|$

那么交换之后的值就是 $sum-t_i-t_j+|a_i-b_j|+|a_j-b_i|$

我们把后面那个东西看成 $(a_i,b_i)$ 与 $(b_j,a_j)$ 的曼哈顿距离

然后就发现这个东西我们可以对于每个 $i$ 求一个最小的 $j$

只需要将绝对值拆开即可，偏序经典题，可以直接上树状数组

时间复杂度 $O(n\log n)$

#include <iostream>
#include <algorithm>
#define maxn 200010
#define lowbit(i) ((i) & (-i))
#define INF 100000000000000000
#define ll long long
using namespace std;

int n, t[maxn];

struct node {
    int x, y, t;
} a[maxn], b[maxn];

int c[maxn * 2], cnt;
void init_hash() {
    for (int i = 1; i <= n; ++i) c[i] = a[i].y, c[i + n] = b[i].y;
    sort(c + 1, c + 2 * n + 1); cnt = unique(c + 1, c + 2 * n + 1) - c - 1;
    for (int i = 1; i <= n; ++i) {
        a[i].y = lower_bound(c + 1, c + cnt + 1, a[i].y) - c; 
        b[i].y = lower_bound(c + 1, c + cnt + 1, b[i].y) - c;
    }
}

ll Bit[2][maxn * 2];
void add(int i, ll v, int o) {
    if (!o) while (i <= cnt) Bit[o][i] = min(Bit[o][i], v), i += lowbit(i);
    else while (i) Bit[o][i] = min(Bit[o][i], v), i -= lowbit(i);
}

ll query(int i, int o) {
    ll s = INF;
    if (!o) while (i) s = min(s, Bit[o][i]), i -= lowbit(i);
    else while (i <= cnt) s = min(s, Bit[o][i]), i += lowbit(i);
    return s;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n; fill(Bit[0], Bit[0] + maxn * 4, INF); ll ans = INF, sum = 0;
    for (int i = 1; i <= n; ++i) cin >> a[i].x, b[i].y = a[i].x;
    for (int i = 1; i <= n; ++i) cin >> a[i].y, b[i].x = a[i].y;
    for (int i = 1; i <= n; ++i) b[i].t = a[i].t = abs(a[i].x - a[i].y), sum += a[i].t;
    init_hash();
    
    sort(a + 1, a + n + 1, [](const node &u, const node &v) { return u.x < v.x; });
    sort(b + 1, b + n + 1, [](const node &u, const node &v) { return u.x < v.x; });
    for (int i = 1, j = 0; i <= n; ++i) {
        while (j < n && b[j + 1].x <= a[i].x) { ++j;
            add(b[j].y, -b[j].x - c[b[j].y] - b[j].t, 0);
            add(b[j].y, -b[j].x + c[b[j].y] - b[j].t, 1);
        }
        ans = min({ ans, sum + query(a[i].y, 0) + a[i].x + c[a[i].y] - a[i].t, sum + query(a[i].y, 1) + a[i].x - c[a[i].y] - a[i].t });
    }

    fill(Bit[0], Bit[0] + maxn * 4, INF);
    sort(a + 1, a + n + 1, [](const node &u, const node &v) { return u.x > v.x; });
    sort(b + 1, b + n + 1, [](const node &u, const node &v) { return u.x > v.x; });
    for (int i = 1, j = 0; i <= n; ++i) {
        while (j < n && b[j + 1].x >= a[i].x) { ++j;
            add(b[j].y, b[j].x - c[b[j].y] - b[j].t, 0);
            add(b[j].y, b[j].x + c[b[j].y] - b[j].t, 1);
        }
        ans = min({ ans, sum + query(a[i].y, 0) - a[i].x + c[a[i].y] - a[i].t, sum + query(a[i].y, 1) - a[i].x - c[a[i].y] - a[i].t });
    }
    cout << ans << "\n";
    return 0;
}