#include <iostream> #include <cmath> using namespace std; #define NUM 1001 int a[NUM]; int select(int left, int right, int k)//选择第k小的数 { if (left >= right) return a[left]; int i = left; int j = right+1; int pivot = a[left]; while (true) { do { i = i+1; } while (a[i] < pivot); do { j = j-1; } while (a[j] > pivot); if (i >= j) break; swap(a[i], a[j]); } if (j-left+1 == k) return pivot; a[left] = a[j]; a[j] = pivot; if (j-left+1 < k) return select(j+1, right, k-j+left-1); else return select(left, j-1, k); } int main() { int n; int x; int y; cin>>n; for (int i=0; i<n; i++) cin>>x>>a[i];//x没用，只要y的平均数 y = select(0, n-1, n/2);//选择第n/2小的数 int min=0; for(int i=0;i<n;i++) min += (int)fabs(a[i]-y); cout<<min<<endl; return 0; }

这段代码实现了一个选择问题，即找到数组中第 k 小的数。代码的实现使用了快速选择算法，其时间复杂度为 O(n)。该算法的基本思想是：通过一次快速排序的划分操作，将数组分成两部分，一部分都小于选定的枢轴（pivot），另一部分都大于等于枢轴。如果枢轴正好是第 k 小的数，那么就找到了答案；否则，如果小于 k，就在右半部分继续查找第 k 小的数；如果大于 k，就在左半部分继续查找第 k 小的数。

该代码也包含了一个应用，即求一个数组中每个数与它的平均数的差的绝对值之和。具体实现方式是：首先找到数组中位数，然后遍历数组，将每个数与中位数的差的绝对值累加起来即可。