士兵
题意
格格兰郡的 N 名士兵随机散落在全郡各地。
格格兰郡中的位置由一对 (x,y) 整数坐标表示。
士兵可以进行移动，每次移动，一名士兵可以向上，向下，向左或向右移动一个单位（因此，他的 x 或 y 坐标也将加 1 或减 1）。
现在希望通过移动士兵，使得所有士兵彼此相邻的处于同一条水平线内，即所有士兵的 y 坐标相同并且 x 坐标相邻。
请你计算满足要求的情况下，所有士兵的总移动次数最少是多少。
需注意，两个或多个士兵不能占据同一个位置。
思路
首先我们可以想到，士兵在 x 轴上的移动和在 y 轴上的移动是互不影响的
对于 y 坐标，将问题转化为 选择 y 轴上的一个点，将所有士兵的 y 坐标移到那个点上的最小步数，可以发现是一个经典的中位数问题，算则所有士兵 y 轴坐标的中位数即可。
对于 x 坐标，不能将其转换为将所有士兵的 x 坐标移动到 x 轴上的某个点，所以不能用中位数问题解决。
因为移动前后所有士兵在 x 轴上的相对位置不发生改变，可以假设第一个士兵 x 1移动后的位置为 a ，第二个士兵 x 2移动后的位置为a+1，以此类推第 n 个士兵移动后的位置为 a+n−1
代码
#include<bits/stdc++.h> #include<unordered_map> // #define int long long #define INF 0x3f3f3f3f #define mod 1000000007 #define rep(i, st, ed) for (int (i) = (st); (i) <= (ed);++(i)) #define pre(i, ed, st) for (int (i) = (ed); (i) >= (st);--(i)) using namespace std; typedef long long LL; typedef pair<int, int> PII; template<typename T> inline T gcd(T a, T b) { return b ? gcd(b, a % b) : a; } template<typename T> inline T lowbit(T x) { return x & -x; } const int N = 1e4 + 10; int n; struct Node { int x; int y; bool operator<(Node& x) { return this->x < x.x; } }node[N]; bool cmp(Node a, Node b) { return a.y < b.y; } void solve() { cin >> n; for (int i = 1; i <= n; ++i) { cin >> node[i].x >> node[i].y; } int res = 0; sort(node + 1, node + 1 + n, cmp); int y = node[(n + 1) / 2].y; for (int i = 1; i <= n; ++i) { res += abs(y - node[i].y); } sort(node + 1, node + 1 + n); for (int i = 1; i <= n; ++i) { node[i].x -= i - 1; } sort(node + 1, node + 1 + n); for (int i = 1; i <= n; ++i) { res += abs(node[(n + 1) / 2].x - node[i].x); } cout << res << endl; } signed main() { // int t; cin >> t; // while (t--) solve(); return 0; }
