描述
有 N 个小松鼠, 它们的家用一个点 x,y 表示, 两个点的距离定义为: 点 (x,y) 和它周围的 8 个点即上下左右四个点和对角的四个点, 距离为 1. 现在 N 个松鼠要走到一个松鼠家去, 求走过的最短距离.
题解
简直就是个高中数学题啊... 蒟蒻数学不好, 学不来呜
松鼠 $i $ 和 $j$ 的距离为 $ \max{\left\vert X_i - X_j \right\vert, \left\vert Y_i - Y_j\right\vert } $
但是我们不能在很短的时间内求出对于所有 $i$ 和 $j$ 的 $\max$, 所以只能通过加绝对值让 $\max$ 去掉.
首先 1. $\max{a, b} = (\left\vert a + b\right\vert + \left\vert a - b\right\vert) \div 2$
并且 2.$ \left\vert \left\vert a\right\vert - \left\vert b\right\vert \right\vert + \left\vert \left\vert a\right\vert + \left\vert b\right\vert \right\vert = \left\vert a - b\right\vert + \left\vert a + b\right\vert$
我们通过式子 1 算出 $ \max{\left\vert X_i - X_j \right\vert, \left\vert Y_i - Y_j\right\vert } = ( \left\vert \left\vert X_i - X_j \right\vert - \left\vert Y_i - Y_j\right\vert \right\vert + \left\vert \left\vert X_i - X_j \right\vert + \left\vert Y_i - Y_j \right\vert \right\vert ) \ div 2$
然后再通过 2 式就变成了 $( \left\vert ( X_i-Y_i ) - (X_j - Y_j) \right\vert + \left\vert (X_i - Y_i) + (X_j - Y_j) \right\vert) \div 2$
令 $a_i = X_i - Y_i $ $b_i = X_i + Y_i$
算出所有的 $\left\vert a_i - a_j \right\vert $ 和 $\left\vert b_i - b_j\right\vert$ 再除 2, 取答案最小的 $i$
算 $\left\vert a_i - a_j \right\vert $ 时需要排序求前缀和计算.
打绝对值累死我了..,
代码
- #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);
- }
来源: http://www.bubuko.com/infodetail-2738601.html