#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小的数的算法，然后求出一个数组中所有数与该数组中位数的差的绝对值之和。

算法的主体是select函数，使用了快速选择算法，其时间复杂度是O(n)。接下来用for循环遍历整个数组，计算每个数与该数组中位数的差的绝对值，最后求和输出。

因此，这段代码的时间复杂度为O(nlogn)，其中n为数组的长度，主要由快速选择算法引起。