BZOJ3170: [Tjoi2013]松鼠聚会(切比雪夫距离转曼…

2018-07-17 03:56:27来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 1524  Solved: 803
[Submit][Status][Discuss]

Description

有N个小松鼠,它们的家用一个点x,y表示,两个点的距离定义为:点(x,y)和它周围的8个点即上下左右四个点和对角的四个点,距离为1。现在N个松鼠要走到一个松鼠家去,求走过的最短距离。

Input

第一行给出数字N,表示有多少只小松鼠。0<=N<=10^5
下面N行,每行给出x,y表示其家的坐标。
-10^9<=x,y<=10^9

Output

表示为了聚会走的路程和最小为多少。

Sample Input

6
-4 -1
-1 -2
2 -4
0 2
0 3
5 -2

Sample Output

20

HINT

Source

emmm,题目给出的是切比雪夫距离,我们需要转化成曼哈顿距离

对于坐标中的每个点$(x, y)$,转化为曼哈顿距离之后是$(\frac{x + y}{2}, \frac{x - y}{2})$

然后枚举一个点$k$,我们需要算的是$\sum_{i = 1}^N |x_k - x_i| + |y_k - y_i|$

暴力拆开之后发现可以用前缀和优化

代码写出来很漂亮qwq。

#include<cstdio>
#include<algorithm>
#define LL long long 
using namespace std;
const int MAXN = 1e5 + 10;
const LL INF = 1e18 + 10;
inline int read() {
    char c = getchar();int x = 0,f = 1;
    while(c < '0' || c > '9'){if(c == '-')f = -1;c = getchar();}
    while(c >= '0' && c <= '9'){x = x * 10 + c - '0',c = getchar();}
    return x * f;
}
LL N, x[MAXN], y[MAXN], sortx[MAXN], sorty[MAXN], sumx[MAXN], sumy[MAXN];
LL QueryX(int l, int r) {
    return sumx[r] - sumx[l - 1];
}
LL QueryY(int l, int r) {
    return sumy[r] - sumy[l - 1];
}
LL calc(LL k) {
    LL posx = lower_bound(sortx + 1, sortx + N + 1, x[k]) - sortx,
        posy = lower_bound(sorty + 1, sorty + N + 1, y[k]) - sorty;
    return posx * sortx[posx] - QueryX(1, posx) - (N - posx) * sortx[posx] + QueryX(posx + 1, N) + 
           posy * sorty[posy] - QueryY(1, posy) - (N - posy) * sorty[posy] + QueryY(posy + 1, N);
}
int main() {
#ifdef WIN32
    freopen("a.in", "r", stdin);
#endif
    N = read();
    for(int i = 1; i <= N; i++) {
        int a = read(), b = read();
        x[i] = sortx[i] = a + b,
        y[i] = sorty[i] = a - b;        
    }
    sort(sortx + 1, sortx + N + 1);
    sort(sorty + 1, sorty + N + 1);
    for(int i = 1; i <= N; i++) 
        sumx[i] = sumx[i - 1] + sortx[i],
        sumy[i] = sumy[i - 1] + sorty[i];
    LL ans = INF;
    for(int i = 1; i <= N; i++)
        ans = min(ans, calc(i));
    printf("%lld", ans >> 1);
    return 0;
}

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:QT 启动shell脚本

下一篇:矩阵(+ - *)