曼哈顿

发表于 更新于 分类于

Problem’s Website

  • 曼哈顿

    Solution

  • 首先我们可以写一个$\Theta(n^2)$的暴力，加上卡常可以拿到70分的好成绩，而且可以用来对拍。
  • 然后说正解，这道题目有很多种解法，这里说两种。
    • 第一种为分治，将横纵坐标分开计算，分别升序排序，然后类似于归并，进行计算，因为这种算法并未出自出题人，所以这里不细讲，请自行看代码理解。
    • 第二种为出题人的解法，我们可以把求ans的式子写出来
      $ans=\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}(|x_i-x_j|+|y_i-y_j|)$
      $=(\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}(|x_i-x_j|))+(\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}(|y_i-y_j|))$
      ，由于式子是独立的，所以我们可以分开计算，我们把其中
      $(\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}(|x_i-x_j|))$拿出来观察，第$i$个空缺（也就是$x_{i+1}-x_i$）
      ，这个空缺会被统计入答案，当且仅当一个点在一侧，另一个点在另一侧，所以这一部分对答案的贡献就是 $2i(n-i)(x_{i+1}-x_i)$。所以我们可以直接排序，时间复杂度为$\Theta(n log n)$.

      Code

  • 分治（$Coded$ $by$ $Jhonson$）

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    #include <bits/stdc++.h>
    using namespace std;

    const int N = 300010;
    int a[N], b[N], c[N];

    inline int get_num()
    {
    	register int now = 0;
    	register char ch = getchar();
    	register bool sign = false;
    	while (!isdigit(ch)) {
    		if (ch == '-') sign = true;
    		ch = getchar();
    	}
    	while (isdigit(ch)) {
    		now = (now << 1) + (now << 3) + ch - '0';
    		ch = getchar();
    	}
    	return (sign == false ? now : -now);
    }

    long long ans = 0;

    inline void solve(int l, int r)
    {
    	if (l == r) return;
    	register int mid = (l + r) >> 1;
    	solve(l, mid), solve(mid + 1, r);
    	register long long ret = 0;
    	for (register int i = mid + 1; i <= r; ++i) {
    		ret += c[i] - c[mid];
    	}
    	for (register int i = l; i <= mid; ++i) {
    		ans += (c[mid] - c[i]) * (r - mid) + ret;
    	}
    }

    int main()
    {
    	freopen("manhattan.in", "r", stdin);
    	freopen("manhattan.out", "w", stdout);
    	register int n;
    	n = get_num();
    	for (register int i = 1; i <= n; ++i) {
    		a[i] = get_num(), b[i] = get_num();
    	}
    	sort(a + 1, a + n + 1);
    	sort(b + 1, b + n + 1);
    	for (register int i = 1; i <= n; ++i) c[i] = a[i];
    	solve(1, n);
    	for (register int i = 1; i <= n; ++i) c[i] = b[i];
    	solve(1, n);
    	printf("%lld\n", ans);
    	fclose(stdin);
    	fclose(stdout);
    	return 0;
    }

  • 正常解法（$Coded$ $by$ $dy(me)$）

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    #define gc getchar()
    #define pc(x) putchar(x)
    #define re register
    typedef long long ll;
    const int Maxn = 300000 + 10;
    inline ll sc() {
        ll xx = 0, ff = 1; char cch = gc;
        while(!isdigit(cch)) {
            if(cch == '-') ff = -1; cch = gc;
        }
        while(isdigit(cch)) {
            xx = (xx << 1) + (xx << 3) + (cch ^ '0'); cch = gc;
        }
        return xx * ff;
    }
    inline void out(ll x) {
        if(x < 0) pc('-'), x = -x;
        if(x >= 10)
            out(x / 10);
        pc(x % 10 + '0');
    }
    int n;
    ll a[Maxn], b[Maxn];
    ll ans;
    int main() {
    	scanf("%d", &n);
    	for(re int i = 1; i <= n; ++i)
    		a[i] = sc(), b[i] = sc();
    	std :: sort(a + 1, a + n + 1);
    	std :: sort(b + 1, b + n + 1);
    	for(re int i = 1; i < n; ++i)
    		ans += (a[i + 1] - a[i]) * i * (n - i);
    	for(re int i = 1; i < n; ++i)
    		ans += (b[i + 1] - b[i]) * i * (n - i);
    	out(ans), pc('\n');
        return 0;
    }
    // Coded by dy.

rp+