(洛谷上也有这题)
最终需要将所有士兵移动到一条水平线上,所以在y轴方向上是一个基础的货仓选址问题,选中位数即可.
很容易就可以看出来x轴上的问题完全独立于y轴.
是这样的:在x轴上散落一些点,需要找到一点p,使得x[i]到p+i的距离之和最小.这里x[i]已经升序排列,显然原本在左边的士兵最终移动到队列左边距离会更短.
现在要求Σi=1 n abs(x[i] - p - i).
即求Σi=1 n abs(x[i] - i - p).
问题变为在x轴上找到一点p,使得a[i]到p的距离之和最小.(a[i] = x[i] - i).
即为货仓选址问题.只需要对a[i]排序并选取中位数位置求解即可.注意这次排序的意义仅仅是为了找到中位数,而不是调整士兵的位置.
#include <algorithm> #include <cstdio> #include <cmath> #include <cstring> #include <iostream> using namespace std; int n, x[10010], y[10010]; long long ans; int main(){ scanf("%d", &n); for(int i = 1; i <= n; i++) scanf("%d%d", x + i, y + i); sort(x + 1, x + n + 1); for(int i = 1; i <= n; i++) x[i] -= i; sort(x + 1, x + n + 1); sort(y + 1, y + n + 1); for(int i = 1; i <= n; i++) ans += abs(y[i] - y[(n + 1) / 2]); for(int i = 1; i <= n; i++) ans += abs(x[i] - x[(n + 1) / 2]); printf("%lld", ans); return 0; }