油井

题目
主油管道为东西向，确定主油管道的南北位置，使南北向油井喷油管道和最小。要求线性时间完成。
1<= 油井数量 <=2 000 000
输入要求：
输入有油井数量行，第 K 行为第 K 油井的坐标 X ,Y 。其中， 0<=X<2^31,0<=Y<231 。
输出要求：
输出有一行， N 为主管道最优位置的最小值
分析：
管道为东西向，则求所有油井南北方向到管道最小距离和。这题虽然给了两个坐标，其实只和油井坐标的Y坐标有关系，就是求所有Y坐标的中位数，中位数对应位置，所有油井到管道距离和最小。
不能用排序。(排序还用你写?)
我们采用分治，能达到Logn的时间复杂度。
采用最坏时间O(n)线性选择算法。见下代码

#include<bits/stdc++.h>  
using namespace std;  int oil[2000005];  
int insertSort(int x) {//找五个数中位数 for(int i = 0; i < 3; i++) {  for(int j = i + 1; j < 5; j++) {  if(oil[x + j] > oil[x + i]) {  swap(oil[x + j], oil[x + i]);  }  }  }  return 0;  
}   
int Partition(int l, int r, int p) {//将all[l.r]以p为基准分开 int i, j;  for(i = l; i <= r; i++) //目的以all[p]为基准划分 {  if(p == oil[i]) {  swap(oil[i], oil[l]);  break;  }  }  i = l, j = r + 1;  //左右同时遍历到第一个符合条件，交换值(类似快速排序思想） while (1){  while (oil[++i] < p && i < r);  while (oil[--j] > p);  if (i >= j)  break;  swap(oil[i],oil[j]);  }  oil[l] = oil[j];  oil[j] = p;  return j;  }   
int select(int l, int r, int k)  {       if(r - l < 75)//小于七十五用普通排序更方便 {   sort(oil + l, oil + r + 1);  return oil[l + k - 1];  }  for(int i = 0; i <= (r - l - 4) / 5; i++) {  insertSort(l + 5*i);  swap(oil[l + i], oil[l + 5*i + 2]);  }  int mid = select(l, l + (r - l - 4) / 5, (r - l - 4) / 10);  int i = Partition(l, r, mid);  int len = i - l + 1;  if(len == k) {  return oil[i];  }  else if(k < len) {  return select(l, i - 1, k);  }  else {  return select(i + 1, r, k - len);  }  }  int main() {  int a, b, n = 0;  while(scanf("%d,%d", &a, &b) != EOF)    {   oil[n++] = b;  }  if(n % 2 == 1)  {  cout << select(0, n - 1, (n + 1) / 2) << endl;  }  else   {  cout << select(0, n - 1, n / 2) << endl;  }  return 0;  
}  

油井

题目
主油管道为东西向，确定主油管道的南北位置，使南北向油井喷油管道和最小。要求线性时间完成。
1<= 油井数量 <=2 000 000
输入要求：
输入有油井数量行，第 K 行为第 K 油井的坐标 X ,Y 。其中， 0<=X<2^31,0<=Y<231 。
输出要求：
输出有一行， N 为主管道最优位置的最小值
分析：
管道为东西向，则求所有油井南北方向到管道最小距离和。这题虽然给了两个坐标，其实只和油井坐标的Y坐标有关系，就是求所有Y坐标的中位数，中位数对应位置，所有油井到管道距离和最小。
不能用排序。(排序还用你写?)
我们采用分治，能达到Logn的时间复杂度。
采用最坏时间O(n)线性选择算法。见下代码

#include<bits/stdc++.h>  
using namespace std;  int oil[2000005];  
int insertSort(int x) {//找五个数中位数 for(int i = 0; i < 3; i++) {  for(int j = i + 1; j < 5; j++) {  if(oil[x + j] > oil[x + i]) {  swap(oil[x + j], oil[x + i]);  }  }  }  return 0;  
}   
int Partition(int l, int r, int p) {//将all[l.r]以p为基准分开 int i, j;  for(i = l; i <= r; i++) //目的以all[p]为基准划分 {  if(p == oil[i]) {  swap(oil[i], oil[l]);  break;  }  }  i = l, j = r + 1;  //左右同时遍历到第一个符合条件，交换值(类似快速排序思想） while (1){  while (oil[++i] < p && i < r);  while (oil[--j] > p);  if (i >= j)  break;  swap(oil[i],oil[j]);  }  oil[l] = oil[j];  oil[j] = p;  return j;  }   
int select(int l, int r, int k)  {       if(r - l < 75)//小于七十五用普通排序更方便 {   sort(oil + l, oil + r + 1);  return oil[l + k - 1];  }  for(int i = 0; i <= (r - l - 4) / 5; i++) {  insertSort(l + 5*i);  swap(oil[l + i], oil[l + 5*i + 2]);  }  int mid = select(l, l + (r - l - 4) / 5, (r - l - 4) / 10);  int i = Partition(l, r, mid);  int len = i - l + 1;  if(len == k) {  return oil[i];  }  else if(k < len) {  return select(l, i - 1, k);  }  else {  return select(i + 1, r, k - len);  }  }  int main() {  int a, b, n = 0;  while(scanf("%d,%d", &a, &b) != EOF)    {   oil[n++] = b;  }  if(n % 2 == 1)  {  cout << select(0, n - 1, (n + 1) / 2) << endl;  }  else   {  cout << select(0, n - 1, n / 2) << endl;  }  return 0;  
}