NC212068 最优公式

zrzring 2020-11-03 PM 21℃ 0条

把问题映射到坐标上就是切比雪夫距离,然后一个套路,切比雪夫距离转曼哈顿距离

$$ A(x, y)\rightarrow A(x - y, y - x) $$

曼哈顿距离的两维坐标互不影响,于是可以转化为两维分别考虑,每一维下的答案就是找一个点使得n个点到该点距离和最近,是个经典题目,于是我们分别对两维坐标求一遍就行

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <queue>
 
using namespace std;
 
const int N = 1e6 + 10, M = 2e6 + 10, inf = 1e9, P = 1e9 + 7;
 
inline int read() {
    bool sym = 0; int res = 0; char ch = getchar();
    while (!isdigit(ch)) sym |= (ch == '-'), ch = getchar();
    while (isdigit(ch)) res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
    return sym ? -res : res;
}
 
int n, cnt, a[N], b[N];
 
long long ans, m, pre[N];
 
long long check(int l) {
    int p1 = 0, p2 = n; long long cnt = 0;
    for (p2 = n; p2 >= 1; p2--) {
        while (a[p1 + 1] + b[p2] <= l && p1 < n) ++p1; cnt += 1ll * p1;
    }
    return cnt;
}
 
void solve() {
    int l = -inf, r = inf;
    while (l < r) {
        int mid = l + r >> 1; check(mid) > m ? r = mid : l = mid + 1;
    }
    int p1 = 0, p2 = n;
    for (p2 = n; p2 >= 1; p2--) {
        while (a[p1 + 1] + b[p2] <= l && p1 < n) ++p1;
        ans = (ans + 1ll * l * p1 - pre[p1] - 1ll * p1 * b[p2]) % P;
        ans = (ans + pre[n] - pre[p1] + 1ll * (n - p1) * b[p2] - 1ll * (n - p1) * l) % P;
        if (ans < 0) {printf("%lld\n", ans); return;}
    }
}
 
int main() {
    n = read(); m = 1ll * n * n / 2ll;
    for (int i = 1; i <= n; i++) a[i] = read(); sort(a + 1, a + n + 1);
    for (int i = 1; i <= n; i++) pre[i] = pre[i - 1] + a[i], b[i] = a[i];
    solve();
    for (int i = 1; i <= n; i++) b[i] = -a[n - i + 1];
    solve(); printf("%lld", ans);
    return 0;
}

评论


您还没有登录呦


登录 注册
Title - Artist
0:00