题意

给出n个点的坐标，它们只能往上、下、左、右一格一格地移动，求使其移动至水平线上的最小步数。

思路

转载

先易后难，对于纵向的问题，我们推个公式，，这个很容易看出是货仓选址问题，k取y[i]的中位数就可以了。对于横向的问题，同样推一下公式，，推到这里，我们把与i相关的项全部合在了一起，只要把x[i]-i看作一个整体，这个子问题也是中位数问题。

代码

//poj1723 #include<cstdio> #include<algorithm> #include<cmath> #define max(a,b) (a>b?a:b) #define min(a,b) (a<b?a:b) #define ll long long using namespace std; #define N 10005 int x[N],y[N]; int ans; int main() { int n; scanf("%d", &n); for (int i = 1; i <= n; i++) scanf("%d%d", &x[i], &y[i]); sort(x + 1, x + 1 + n); sort(y + 1, y + 1 + n); for (int i = 1; i <= n; i++) x[i] -= i; sort(x + 1, x + 1 + n); int midx = x[(n+1) / 2]; int midy = y[(n+1) / 2]; for (int i = 1; i <= n; i++) ans += abs(midx-x[i])+abs(midy-y[i]); printf("%d\n", ans); return 0; }

 

转载于:https://www.cnblogs.com/lincold/p/10160810.html