很容易理解题目的意思，就是求某个点到其他点的距离之和，而且要让这个和最小，很明显是求中位数了。
关于求中位数，一般的方法是我们先将整个数组进行排序，然后直接取出中位数，采用不同的排序方法可能有不同的时间复杂度，一般我们使用快排，时间复杂度为O(nlogn)，有没有更快的方法？ 答案是肯定的。
这里有一种时间复杂度为O(n)的算法，下面是此题的解题代码。
//uva 10041 - Vito's Family #include <stdio.h> #include <algorithm> #include <math.h> using namespace std; int a[40000]; int partition(int l, int r) { int x = a[r]; int i = l-1; for (int j = l; j < r; j++) { if (x >= a[j]) { i++; swap(a[i], a[j]); } } ++i; swap(a[i],a[r]); return i; } int select(int l, int r, int k) { if (l >= r) return a[l]; int p = partition(l, r); if (k == p) return a[k]; else if(k > p) return select(p + 1, r, k); else return select(l, p - 1, k); } int main() { int t, n; scanf("%d",&t); while (t--) { scanf("%d",&n); for (int i = 0; i < n; i++) scanf("%d",&a[i]); int x = select(0, n-1, n/2); int s = 0; for (int i = 0; i < n; i++) { s += abs(a[i] - x); } printf("%d\n",s); } return 0; }
了解快排的人对int (int l, int r) 这个函数很熟悉，因为这是在快排中用到的，它的作用是对数组的某一段选一个分界点，使得该点左边的数都不大于该点的数，右边的点不小于该点的数，也就是说我们通过一次调用这个函数确定一个数的位置，快排是将该点两边分别进行递归操作，时间复杂度为O(nlogn)，而select只是对一边进行递归操作（有点像二分的递归形式），所以时间复杂度仅为O(n)。
其实还有时间复杂度更低的算法，划分树。。。 时间复杂度为log(n) 。。。。。 划分树的优点是可以对某个区间进行多次的查询，并不改变原序。
poj 2388 //poj 2388 #include <stdio.h> #include <algorithm> using namespace std; const int maxn = 10005; int a[maxn]; int partition(int l, int r) { int x = a[r]; int ol = l; for (int i = l; i < r; i++) { if (a[i] < x) { swap(a[ol], a[i]); ol++; } } swap(a[r], a[ol]); return ol; } int search(int l, int r, int k) { int pos = partition(l, r); if (l == r) return a[l]; if (k == pos) return a[k]; else if (pos < k) return search(pos+1, r, k); else if (pos > k) return search(l, pos-1, k); } int main() { int n; while (scanf("%d", &n) != EOF) { for (int i = 0; i < n; i++) scanf("%d",&a[i]); printf("%d\n",search(0, n-1, n/2)); } return 0; }
