Cptraser/ 十月 28, 2018/ 2018.10/ 0 comments

[TJOI2013]松鼠聚会

题面传送门

原题的距离其实就是切比雪夫距离,转换成曼哈顿距离做前缀和。
新点为:(\frac{x+y}{2},\frac{x-y}{2})
类似Wanafly18T3

#include<cstring>
#include<cstdio>
#include<algorithm>
#define rd read()
#define ll long long
using namespace std;

const int N = 2e5;

ll sumx[N], sumy[N], n, ans = 1e18;

struct node {
    ll x, y;
    ll xx, yy;
    ll disx, disy;
}a[N];

ll read() {
    ll X = 0, p = 1; char c = getchar();
    for(; c > '9' || c < '0'; c = getchar()) if(c == '-') p = -1;
    for(; c >= '0' && c <= '9'; c = getchar()) X = X * 10 + c - '0';
    return X * p;
}

int cmpx(const node &A, const node &B ) {
    return A.xx < B.xx;
}

int cmpy(const node &A, const node &B) {
    return A.yy < B.yy;
}

int main()
{
    n = rd;
    for(int i = 1; i <= n; ++i) {
        a[i].x = rd * 2;
        a[i].y = rd * 2;
        a[i].xx = (a[i].x + a[i].y) >> 1;
        a[i].yy = (a[i].x - a[i].y) >> 1;
    }
    sort(a+1, a+1+n, cmpx);
    for(int i = 1; i <= n; ++i) sumx[i] = sumx[i - 1] + a[i].xx;
    for(int i = 1; i <= n; ++i) {
        a[i].disx = a[i].xx * i - sumx[i];
        a[i].disx += sumx[n] - sumx[i] - (n - i) * a[i].xx;
    }
    sort(a+1, a+1+n, cmpy);
    for(int i = 1; i <= n; ++i) sumy[i] = sumy[i - 1] + a[i].yy;
    for(int i = 1; i <= n; ++i) {
        a[i].disy = a[i].yy * i - sumy[i];
        a[i].disy += sumy[n] - sumy[i] - (n - i) * a[i].yy;
        if(a[i].disy + a[i].disx < ans) ans = a[i].disx + a[i].disy;
    }
    printf("%lld\n", ans >> 1);
}
Share this Post

Leave a Comment

电子邮件地址不会被公开。 必填项已用*标注

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>
*
*