poj2106，poj 1723 中位数

　　最近在看一些中位数的东西，然后顺便也看了些题目。poj 1723不仅要求到水平位置的最短距离和，还要求水平都相邻的排成一排的最短距离和，即士兵都站成一列。

　　到y轴的距离好办，按y轴坐标排序，求中位数，然后求所有到中位数的距离和。

　　但是在x上怎么样才能最短呢？百思不得其解啊，最后看了这篇之后，豁然开朗。

　　x轴方向，先把x[]排好序，要想移动的距离最短，那么这时的相对位置肯定不变。那么假设a是这个队列的最左边的x坐标，那么它们的关系就有就有

     x[0] -> a

　　x[1]  -> a + 1

　　x[2] -> a + 2

　　........

　　x[i] -> a + i

　　即

     x[0] -> a

　　x[1] - 1 -> a

　　x[2] - 2 -> a

　　.......

　　x[i] - i -> a

　　也就是要把这些点移动到固定的一个点，那么我们只要求出x[i]-i的中位数，就可以求出x轴移动的最短距离了。

　　那么我们就可以这样来做：对x，y排序， 然后再对x进行x[i] = x[i] - i，再排序，去除两个中位数，分别求距离的绝对值即可。

代码：

//poj 1732
#include <stdio.h>
#include <stdlib.h>
#include <math.h>int n;
int *x, *y;int cmp(const void *a, const void *b)
{return *(int *)a - *(int *)b;
}void input()
{int i = 0;
/*FILE *fp;fp = fopen("in.txt","r");if (fp == NULL){printf("FOPEN ERROR\n");return;}
*/scanf("%d",&n);//fscanf(fp,"%d",&n);x = (int *)malloc(sizeof(int)*n);y = (int *)malloc(sizeof(int)*n);while (i < n){scanf("%d%d",x+i,y+i);//fscanf(fp,"%d%d",x+i,y+i);i++;}
}void free_buf()
{free(x);free(y);
}int main()
{int sum = 0, i;int mid_x, mid_y;input();qsort(y,n,sizeof(int),cmp);qsort(x,n,sizeof(int),cmp);for (i = 0; i < n; i++){*(x+i) = *(x+i) - i;}qsort(x,n,sizeof(int),cmp);mid_y = *(y + n/2);mid_x = *(x + n/2);for (i = 0; i < n; i++){sum += abs(*(y+i) - mid_y);sum += abs(*(x+i) - mid_x);}printf("%d\n",sum);free_buf();return 0;}

2013/7/25 23:41