最近在看一些中位数的东西,然后顺便也看了些题目。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