【算法实践】1.1 油井问题——线性时间内完成（分治 中位数）

主油管道为东西向，确定主油管道的南北位置，使南北向油井喷油管道和最小。要求线性时间完成。

#include "stdio.h"#include "vector"using namespace std;vector<int> map;int part(int l, int r, int m){int i = l, j = r;int x = map[l];while (i < j){while (i < j && map[j] >= x){j--;}if (i < j){map[i++] = map[j];}while (i < j && map[i] <= x){i++;}if (i < j){map[j--] = map[i];}}map[i] = x;return i;}void find(int m){int i = -1, l = 0, r = map.size() - 1;while (true){i = part(l, r, m);if (i < m){l = i + 1;}else if (i > m){r = i - 1;}else{break;}}}int main(int argc, char const *argv[]){int x, y;while (scanf("%d,%d", &x, &y) != EOF){map.push_back(y);}int n = map.size();int m;if (n % 2 == 0){m = n / 2 - 1;}else{m = n / 2;}find(m);printf("%d\n", map[m]);return 0;}