描述
有N个小松鼠，它们的家用一个点x,y表示，两个点的距离定义为：点(x,y)和它周围的8个点即上下左右四个点和对角的四个点，距离为1。现在N个松鼠要走到一个松鼠家去，求走过的最短距离。
题解
简直就是个高中数学题啊。。。蒟蒻数学不好，学不来呜
松鼠$i $ 和 $j$ 的距离为$ max{leftvert X_i - X_j ightvert, leftvert Y_i - Y_j ightvert } $
但是我们不能在很短的时间内求出对于所有$i$和$j$ 的$max$， 所以只能通过加绝对值让$max$去掉。
首先1. $max{a, b} = (leftvert a + b ightvert + leftvert a - b ightvert) div 2$
并且 2.$ leftvert leftvert a ightvert - leftvert b ightvert ightvert + leftvert leftvert a ightvert + leftvert b ightvert ightvert = leftvert a - b ightvert + leftvert a + b ightvert$
我们通过式子1算出$ max{leftvert X_i - X_j ightvert, leftvert Y_i - Y_j ightvert } = ( leftvert leftvert X_i - X_j ightvert - leftvert Y_i - Y_j ightvert ightvert + leftvert leftvert X_i - X_j ightvert + leftvert Y_i - Y_j ightvert ightvert ) div 2$
然后再通过2式就变成了 $( leftvert ( X_i-Y_i ) - (X_j - Y_j) ightvert + leftvert (X_i - Y_i) + (X_j - Y_j) ightvert) div 2$
令$a_i = X_i - Y_i $ $b_i = X_i + Y_i$
算出所有的$leftvert a_i - a_j ightvert $ 和$leftvert b_i - b_j ightvert$ 再除 2， 取答案最小的$i$
算$leftvert a_i - a_j ightvert $ 时需要排序求前缀和计算。
打绝对值累死我了。。、
代码
1 #include<cstring> 2 #include<cstdio> 3 #include<algorithm> 4 #define rd read() 5 #define ll long long 6 using namespace std; 7 8 const int N = 2e5; 9 10 ll sumx[N], sumy[N], n, ans = 1e18; 11 12 struct node { 13 ll x, y; 14 ll xx, yy; 15 ll disx, disy; 16 }a[N]; 17 18 ll read() { 19 ll X = 0, p = 1; char c = getchar(); 20 for(; c > '9' || c < '0'; c = getchar()) if(c == '-') p = -1; 21 for(; c >= '0' && c <= '9'; c = getchar()) X = X * 10 + c - '0'; 22 return X * p; 23 } 24 25 int cmpx(const node &A, const node &B ) { 26 return A.xx < B.xx; 27 } 28 29 int cmpy(const node &A, const node &B) { 30 return A.yy < B.yy; 31 } 32 33 int main() 34 { 35 n = rd; 36 for(int i = 1; i <= n; ++i) { 37 a[i].x = rd * 2; 38 a[i].y = rd * 2; 39 a[i].xx = (a[i].x + a[i].y) >> 1; 40 a[i].yy = (a[i].x - a[i].y) >> 1; 41 } 42 sort(a+1, a+1+n, cmpx); 43 for(int i = 1; i <= n; ++i) sumx[i] = sumx[i - 1] + a[i].xx; 44 for(int i = 1; i <= n; ++i) { 45 a[i].disx = a[i].xx * i - sumx[i]; 46 a[i].disx += sumx[n] - sumx[i] - (n - i) * a[i].xx; 47 } 48 sort(a+1, a+1+n, cmpy); 49 for(int i = 1; i <= n; ++i) sumy[i] = sumy[i - 1] + a[i].yy; 50 for(int i = 1; i <= n; ++i) { 51 a[i].disy = a[i].yy * i - sumy[i]; 52 a[i].disy += sumy[n] - sumy[i] - (n - i) * a[i].yy; 53 if(a[i].disy + a[i].disx < ans) ans = a[i].disx + a[i].disy; 54 } 55 printf("%lld ", ans >> 1); 56 }