題目大意是給定n個點的坐標（n <= 10000），問把這些點移動到一橫行并且一個挨著一個（具體位置任意）的最少移動步數(shù)（其中每次只能向上下左右移動一個坐標）。
這個題目體現(xiàn)了轉(zhuǎn)化的思想。首先考慮這樣的問題：一個數(shù)軸上有n個坐標，問把這n個坐標移動到一個點上最少移動步數(shù)，其中每次移動一個格子。根據(jù)中位數(shù)的定義，把所有坐標排序后第n / 2個坐標是中位數(shù)，把所有坐標移動到這上面移動次數(shù)最小。證明很容易想到，因為如果不這樣的話，把目標坐標往左平移還是往右平移，勢必造成左半部的坐標集體變化1，右半部的坐標也集體變化1，如果左右半部坐標的個數(shù)不同，那么顯然就不是最優(yōu)的了。
接下來考慮題目，題目中x和y的移動是孤立的，可以分開討論。y的移動方法和上面討論的情況一樣，現(xiàn)在考慮x的移動。x的移動要求最終是一個挨著一個的，x排好序之后，假設最終所有點以x0為左端點依次排開，對應的點分別為x0, x1...那么問題的答案就等于把這n個坐標依次對應的挪到x0到xn-1上的步數(shù)。如果我們把這n個目標點分別都移動到x0上，那么問題就轉(zhuǎn)化成了中位數(shù)問題了。考慮把xi移動到x0上，要花費i步，為了保證問題是等價變換的，應該把xi在原坐標中對應的xi'也相應的向左移動i步，這樣xi'移動到xi的代價就是不變的。設xi'左移i步后的新位置是xi''，那么問題就轉(zhuǎn)化成：把x0''到xn-1''這n個點移動到一個坐標的最小步數(shù)，用中位數(shù)的方法就可以做出來了。
這個題目的巧妙之處在于把一個未知問題轉(zhuǎn)化成一個已知問題。轉(zhuǎn)化的思想在數(shù)學中用的很多，應該多多練習。
題目代碼：
#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 閱讀(257)
評論(0) 編輯 收藏 引用 所屬分類:
Algorithm - Ad Hoc