POJ1723⼠兵排队C语⾔实现
**
POJ 1723 ⼠兵排队 C语⾔实现
**
**
原⽂
**
Description
N soldiers of the land Gridland are randomly scattered around the country.
A position in Gridland is given by a pair (x,y) of integer coordinates. Soldiers can move - in one move, one soldier can go one unit up, down, left or right (hence, he can change either his x or his y coordinate by 1 or -1).
The soldiers want to get into a horizontal line next to each other (so that their final positions are (x,y), (x+1,y), …, (x+N-1,y), for some x and y). Integers x and y, as well as the final order of soldiers along the horizontal line is arbitrary.
The goal is to minimise the total number of moves of all the soldiers that takes them into such configuration.
Two or more soldiers must never occupy the same position at the same time.
Input
The first line of the input contains the integer N, 1 <= N <= 10000, the number of soldiers.
The following N lines of the input contain initial positions of the soldiers : for each i, 1 <= i <= N, the (i+1)st line of the input file contains a pair of integers x[i] and y[i] separated by a single blank character, representing the coordinates of the ith soldier, -10000 <= x[i],y[i] <= 10000.
Output
The first and the only line of the output should contain the minimum total number of moves that takes the soldiers into a horizontal line next to each other.
Sample Input
5
1 2
2 2
1 3
3 -2
3 3
Sample Output
8
翻译
格格兰郡的N名⼠兵随机散落在全郡各地。
格格兰郡中的位置由⼀对(x,y)整数坐标表⽰。
⼠兵可以进⾏移动，每次移动，⼀名⼠兵可以向上，向下，向左或向右移动⼀个单位（因此，他的x或y坐标也将加1或减1）。
现在希望通过移动⼠兵，使得所有⼠兵彼此相邻的处于同⼀条⽔平线内，即所有⼠兵的y坐标相同并且x坐标相邻。
请你计算满⾜要求的情况下，所有⼠兵的总移动次数最少是多少。
需注意，两个或多个⼠兵不能占据同⼀个位置。
输⼊格式
第⼀⾏输⼊整数N，代表⼠兵的数量。
接下来的N⾏，每⾏输⼊两个整数x和y，分别代表⼀个⼠兵所在位置的x坐标和y坐标，第i⾏即为第i个⼠兵的坐标(x[i],y[i])。
输出格式
输出⼀个整数，代表所有⼠兵的总移动次数的最⼩值。
数据范围
1≤N≤10000
,
−10000≤x[i],y[i]≤10000冒泡排序代码c语言
输⼊样例：
5
1 2
2 2
1 3
3 -2
3 3
输出样例：
8
解题思路
这道题主要考察中位数的应⽤
想要求⾛的最短路径，则需要知道怎样移动可以使步数最少
我们不妨将 x, y 坐标分开来看，想要移到同⼀条⽔平线上， 则需要最终的结果y 相同， x依次相邻， 且如果最左边的⼈的位置是x[a], 则最右边的⼈的坐标是x[a+N]
进⼀步，需要将此问题转化到数学模型。⼤家在中学阶段⼀定见过类似于求解 | x - 4 | + | 7 - x | + | 10 - x |最⼩值的问题，结果应该是当取到所以零点的中位数时，整体的值最⼩。如果不能直接记住结论则可以进⾏⼀个简单的归纳。即， 当只有⼀个的时候， 取该值，当有两个的时候取任意⼀个端点， 当有三个的时候则取中间的，有四个的时候则第⼆个或者第三个都可以。
再回到上⽂我们可以知道，最终结果的这条⽔平线的y 坐标应该是 这些 y 值得中位数。因为这个这个问题在 y ⽅向上的结果应该是 | ( y[i] - mid_y ) | + | ( y[i+1] - mid_y ) | +…+ | ( y[i+N-1] - mid_y ) |的最⼩值，所以代⼊中位数即可。
于是我们将 y 坐标进⾏排序，排序后中间的数即为中位数
y ⽅向上的步数⽐较好确定，那 x 轴⽅向上的呢？
我们不妨先看⼀下 x 轴上的步数求解的数学公式是什么样⼦的。我们假设这条线的第⼀个⼈的横坐标是A ， 由于站成⼀排后横坐标是连续的， 所以接下来的横坐标依次是 A+1， A+2， … A+N-1；不妨将1 到 N 设置为循环变量 i, 则可以表⽰为 A+ i , 设每⼀点的横坐标为 x[ i ], 则对于每⼀点来说 移动的距离是 | A + i - x[ i ] |, i 从 0 到 N-1 这同样是⼀个绝对值排序问题，所以也应该我们也需要到 x 的中位数， 我们为了便于排序， 设⼀个新的数组为 x[i] = x[i] - i; 经过这⼀步转换之后原问题则变成 | A - x[ i ] |
然后⽤⼀个循环进⾏相加即可
在处理 x 坐标时我们要知道横坐标的左右相对位置是没有变得，意思是原来相对在左的还是在左， 相对在右的还是在右，只有这样才会让x ⽅向上的移动步数最少
总结⼀下就是现将 y 坐标排序，到 y ⽅向上的中位数，将 y ⽅向上的步数求出来，然后是稍微⿇烦⼀点的 x 轴， 先将x 轴进⾏⼀下排序， 现将 x 的坐标进⾏⼀下变换，然后再排序到中位数， 进⽽累加求和
注意
这道题的空间与时间都不是⽆限的，可以看到这道题需要多次排序。所以我们就要尤其的注意时间复杂度。⼀般常⽤的冒泡排序等会出现超时现象。所以这道题可以使⽤ C++ STL 的 快速排序， 即 sort函数， 但是要想使⽤ Ｃ语⾔实现的话就需要⼀个空间复杂度较低的⽅法，我这次采⽤的是　，　（转载），这个是⼀个⽐较稳定且复杂度为　ｎｌｏｇ２ｎ的复杂度，⽤空间换时间，另外题中说-10000 <= x[i],y[i] <= 10000，　也要注意
下⾯是AC代码
#include <stdio.h>
#include <stdlib.h>  //包含 malloc 函数
#include <math.h> //包含 abs()函数mysql服务无法启动是什么
#define MAX_soldier 10000  //采⽤宏定义
免费机器人api接口
//声明归并排序函数原型
void merge(int arr[], int low, int mid, int high);
void merge_sort(int arr[], unsigned int first, unsigned int last);
int main()
{
int x[MAX_soldier], y[MAX_soldier], ;
int i=0,j=0, total_soldier; // total_soldier 是题⽬中第⼀⾏需要输⼊的⼠兵的个数
int mid_x, mid_y, step=0;  // mid_x, mid_y 分别表⽰ x , y ⽅向上的中位数
//输⼊数据
scanf("%d",&total_soldier);
for(i=0;i<total_soldier;++i)
scanf("%d %d",&x[i], &y[i]);
//对 x , y ⽅向上的数据进⾏归并排序
merge_sort(y,0,total_soldier-1);
merge_sort(x,0,total_soldier-1);
//求 y ⽅向上的中位数
minor diametermid_y = y[(total_soldier+1)/2-1];
//进⾏数组转换
c语言编程培训班for(i=0;i<total_soldier;++i)
x[i]-=i;
//再次对 x 坐标排序
merge_sort(x,0,total_soldier-1);
/
/求x ⽅向中位数
mid_x = x[(total_soldier+1)/2-1];
//累加求和
for(i=0; i<total_soldier; ++i)
step+=abs(y[i] - mid_y) + abs(x[i] - mid_x);
printf("%d",step);
return 0;
}
//定义归并排序函数
void merge(int arr[], int low, int mid, int high)
{vba数组
int i, k;
int *tmp = (int *)malloc((high-low+1)*sizeof(int));
//申请空间，使其⼤⼩为两个
int left_low = low;
int left_high = mid;
int right_low = mid + 1;
int right_high = high;
int right_high = high;
for(k=0; left_low<=left_high && right_low<=right_high; k++)
{  // ⽐较两个指针所指向的元素
if(arr[left_low]<=arr[right_low])
{
tmp[k] = arr[left_low++];
}
else
{
tmp[k] = arr[right_low++];
}
}
if(left_low <= left_high)
{  //若第⼀个序列有剩余，直接复制出来粘到合并序列尾
//memcpy(tmp+k, arr+left_low, (left_high-left_low+l)*sizeof(int));
for(i=left_low;i<=left_high;i++)
tmp[k++] = arr[i];
}
if(right_low <= right_high)
{
//若第⼆个序列有剩余，直接复制出来粘到合并序列尾
//memcpy(tmp+k, arr+right_low, (right_high-right_low+1)*sizeof(int));        for(i=right_low; i<=right_high; i++)
tmp[k++] = arr[i];
}
for(i=0; i<high-low+1; i++)
arr[low+i] = tmp[i];
free(tmp);
return;
}
void merge_sort(int arr[], unsigned int first, unsigned int last)
{
int mid = 0;
if(first<last)
{
mid = (first+last)/2; /* 注意防⽌溢出 */
/*mid = first/2 + last/2;*/
//mid = (first & last) + ((first ^ last) >> 1);
merge_sort(arr, first, mid);
merge_sort(arr, mid+1,last);
merge(arr,first,mid,last);
}
return;
}