题目大意是给定n个点的坐标（n <= 10000），问把这些点移动到一横行并且一个挨着一个（具体位置任意）的最少移动步数（其中每次只能向上下左右移动一个坐标）。
这个题目体现了转化的思想。首先考虑这样的问题：一个数轴上有n个坐标，问把这n个坐标移动到一个点上最少移动步数，其中每次移动一个格子。根据中位数的定义，把所有坐标排序后第n / 2个坐标是中位数，把所有坐标移动到这上面移动次数最小。证明很容易想到，因为如果不这样的话，把目标坐标往左平移还是往右平移，势必造成左半部的坐标集体变化1，右半部的坐标也集体变化1，如果左右半部坐标的个数不同，那么显然就不是最优的了。
接下来考虑题目，题目中x和y的移动是孤立的，可以分开讨论。y的移动方法和上面讨论的情况一样，现在考虑x的移动。x的移动要求最终是一个挨着一个的，x排好序之后，假设最终所有点以x0为左端点依次排开，对应的点分别为x0, x1...那么问题的答案就等于把这n个坐标依次对应的挪到x0到xn-1上的步数。如果我们把这n个目标点分别都移动到x0上，那么问题就转化成了中位数问题了。考虑把xi移动到x0上，要花费i步，为了保证问题是等价变换的，应该把xi在原坐标中对应的xi'也相应的向左移动i步，这样xi'移动到xi的代价就是不变的。设xi'左移i步后的新位置是xi''，那么问题就转化成：把x0''到xn-1''这n个点移动到一个坐标的最小步数，用中位数的方法就可以做出来了。
这个题目的巧妙之处在于把一个未知问题转化成一个已知问题。转化的思想在数学中用的很多，应该多多练习。
题目代码：
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 10010;
int main()
{
int x[N], y[N], n;
while (scanf("%d", &n) == 1)
{
for (int i = 0; i < n; i++)
scanf("%d %d", &x[i], &y[i]);
sort(x, x + n);
sort(y, y + n);
for (int i = 0; i < n; i++)
x[i] -= i;
sort(x, x + n);
int ans = 0;
for (int i = 0; i < n / 2; i++)
ans += x[n-i-1] - x[i] + y[n-1-i] - y[i];
printf("%d\n", ans);
}
return 0;
}
posted on 2009-06-25 10:13
sdfond 阅读(251)
评论(0) 编辑 收藏 引用 所属分类:
Algorithm - Ad Hoc