编程习题：士兵站队问题
效云 李
士兵站队问题
«问题描述：
在一个划分成网格的操场上，n个士兵散乱地站在网格点上。网格点由整数坐标(x,y)表示。士兵们可以沿网格边上、下、左、右移动一步，但在同一时刻任
一网格点上只能有一名士兵。按照军官的命令，士兵们要整齐地列成一个水平队列，即排列成(x,y),(x+1,y),…,(x+n-1,y)。如何选择
x和y的值才能使士兵们以最少的总移动步数排成一列。
«编程任务：
计算使所有士兵排成一行需要的最少移动步数。
«数据输入：
由文件sol*.in提供输入数据。文件的第1行是士兵数n，1£n£10000。接下来n行是士兵的初始位置，每行2个整数x和
y，-10000£x，y£10000。
«结果输出:
程序运行结束时，将计算结果输出到文件sol*.out中。文件的第1行中的数是士兵排成一行需要的最少移动步数。
输入文件示例
输出文件示例
5
1 2
2 2
1 3
3 -2
3 3
sol0.out
8
我的C++代码：
#pragma once
class Point
{
public:
Point(void);
int getX();
int getY();
void setX(int);
void setY(int);
public:
~Point(void);
private:
int x;
int y;
};
#include "StdAfx.h"
#include "Point.h"
Point::Point(void)
{
}
Point::~Point(void)
{
}
int Point::getX()
{
return x;
}
int Point::getY()
{
return y;
}
void Point::setX(int newx)
{
x=newx;
}
void Point::setY(int newy)
{
y=newy;
}
// 递归分治-士兵站队问题.cpp : Defines the entry point for the console
application.
//
#include "stdafx.h"
#include "Point.h"
#include<iostream>
#include<fstream>
#include<vector>
using namespace std;
int _tmain(int argc, _TCHAR* argv[])
{
int n=0;
ifstream finput;
finput.open("input.txt");
finput>>n;
vector<Point> v(n+1);
int i=0,temp=0;
for(i=1;i<=n;++i)
{
finput>>temp;
v[i].setX(temp);
finput>>temp;
v[i].setY(temp);
}
finput.close();
int get_middle_x(vector<Point>&,int,int,int);
int (*p_get_middle_x)(vector<Point>&,int,int,int);
p_get_middle_x=get_middle_x;
int middle_x=(*p_get_middle_x)(v,1,n,(1+n)/2);
int opt_result_x(int,int);
int (*p_opt_result_x)(int,int);
p_opt_result_x=opt_result_x;
int op_result_x=(*p_opt_result_x)(middle_x,n);
int now_opt_result_x(int,int,vector<Point>&);
int (*p_now_opt_result_x)(int,int,vector<Point>&);
p_now_opt_result_x=now_opt_result_x;
int now_result_x=(*p_now_opt_result_x)(middle_x,n,v);
int step_x=op_result_x-now_result_x;
int get_middle_y(vector<Point>&,int,int,int);
int (*p_get_middle_y)(vector<Point>&,int,int,int);
p_get_middle_y=get_middle_y;
int middle_y=(*p_get_middle_y)(v,1,n,(1+n)/2);
int get_step_y(int,int,vector<Point>&);
int (*p_get_step_y)(int,int,vector<Point>&);
p_get_step_y=get_step_y;
int step_y=(*p_get_step_y)(middle_y,n,v);
int total_result=step_x+step_y;
ofstream foutput;
foutput.open("output.txt");
foutput<<total_result;
foutput.close();
return 0;
}
int get_step_y(int middle_y,int n,vector<Point>& v)
{
int result=0,i=0;
int abs1(int);
for(i=1;i<=n;++i)
{
result+=abs1(v[i].getY()-middle_y);
}
return result;
}
int now_opt_result_x(int middle_x,int n,vector<Point>& v)
{
int result=0;
int abs1(int);
int (*p_abs1)(int);
p_abs1=abs1;
for(int i=1;i<=n;++i)
{
result+=(*p_abs1)(v[i].getX()-middle_x);
}
return result;
}
int abs1(int n)
{
if(n>=0) return n;
else return -n;
}
int opt_result_x(int middle_x,int n)
{
int j=n/2;
int result=0;
for(int i=1;i<=j;++i)
{
result+=i;
}
return 2*result;
}
int get_middle_x(vector<Point>& v,int begin,int end,int k)
{
int partition(vector<Point>&,int,int);
int (*p_partition)(vector<Point>&,int,int);
p_partition=partition;
if(begin==end) return v[begin].getX();
int i=(*p_partition)(v,begin,end);
int j=i-begin+1;
if(k<=j) return get_middle_x(v,begin,i,k);
else return get_middle_x(v,i+1,end,k-j);
}
int get_middle_y(vector<Point>& v,int begin,int end,int k)
{
int partition_y(vector<Point>&,int,int);
int (*p_partition_y)(vector<Point>&,int,int);
p_partition_y=partition_y;
if(begin==end) return v[begin].getY();
int i=(*p_partition_y)(v,begin,end);
int j=i-begin+1;
if(k<=j) return get_middle_y(v,begin,i,k);
else return get_middle_y(v,i+1,end,k-j);
}
int partition_y(vector<Point>&v,int begin,int end)
{
Point temp=v[begin];
int pivotkey=v[begin].getY();
while(begin<end)
{
while(begin<end&&v[end].getY()>=pivotkey) --end;
v[begin]=v[end];
while(begin<end&&v[begin].getY()<=pivotkey) ++begin;
v[end]=v[begin];
}
v[begin]=temp;
return begin;
}
int partition(vector<Point>&v,int begin,int end)
{
Point temp=v[begin];
int pivotkey=v[begin].getX();
while(begin<end)
{
while(begin<end&&v[end].getX()>=pivotkey) --end;
v[begin]=v[end];
while(begin<end&&v[begin].getX()<=pivotkey) ++begin;
v[end]=v[begin];
}
v[begin]=temp;
return begin;
}
higer
higer
士兵数：0<n<=10000 坐标范围：-10000<=X<=10000 -10000<=Y<=10000
一 士兵有多种移动方式
通过适当的移动顺序和移动路线可以使得同一时刻不会有两名士兵站在同一点
二 题目要求最佳移动方式（即求移动的最少步数）
题目要求转化为求士兵站立的“最终位置”，即如何取“最终位置”使得士兵移动的步数最少（最优）
Y轴方向上的考虑
设目标坐标为M，即n个士兵最终需要移动到的Y轴的坐标值为M
n个士兵的Y轴坐标分别为：
Y0，Y1，Y2 …… …… Yn-1
则最优步数S=|Y0-M|+|Y1-M|+|Y2-M|+ …… …… +|Yn-1-M|
结论：M取中间点的值使得S为最少（最优）
证明：……
从最上和最下的两个士兵开始递推……
最优位置
最优位置
归结到最后，处于中间位置的士兵的Y轴坐标值就是“最终位置”的Y轴坐标
可能有两种情况
士兵总数为双数情况：取中间两点间的任意一个位置
士兵总数为单数情况：取中间点的所在位置
解决办法：对所有的Y轴坐标进行排序（O（nlogn））或者进行线性时间选择（O（n））
然后取“中间”点的Y轴坐标值作为最佳位置M的值
最后通过公式求出Y轴方向上移动的最优步数
X轴方向上的考虑
首先需要对所有士兵的X轴坐标值进行排序
然后，按从左至右的顺序依次移动到每个士兵所对应的“最终位置”（最优），所移动的步数总和就是X轴方向上需要移动的步数
例，最左的士兵移动到“最终位置”的最左那位，第二个士兵移动到“最终位置”的第二位
则总的步数为：士兵一移动步数+士兵二移动步数+ …… +士兵n移动步数
如何确定X轴方向上的最佳的“最终位置”？
共n个士兵
他们相应的X轴坐标为：X0，X1，X2 …… …… Xn-1
设，士兵需要移动到的“最终位置”的X轴坐标值为：k，k+1，k+2 …… …… k+（n-1）
则所求最优步数S=|X0-k|+|X1- （k+1） |+|X2-（k+2）|+ …… +|Xn-1-（k+（n-1））|
经过变形S=|X0-k|+|（X1-1）-k|+|（X2-2）-k|+ …… …… +|（Xn-1-（n-1））-k|
注意到公式的形式与Y轴方向上的考虑一样，同样是n个已知数分别减去一个待定数后取绝对值，然后求和
因此还是采用取中位数的办法求得k值，最后算出最优解
higer
/
************************************************************************/
/* 士兵站队问题 */
/
************************************************************************/
#include "stdio.h"
#include "stdlib.h"
#include "string.h"
#define NUM 100
void swap(int& a,int& b){//交换函数
int temp=a;
a=b;
b=temp;
}
int partion(int* a,int p,int r){//快排算法中的分割函数
int i=p,j=r+1;
int x=a[p];
while (1==1) {
while(a[++i]<x&&i<r);//<x的元素都在左边
while(a[--j]>=x&&j>p);//>=x的元素都在右边
if(i>=j) break;
swap(a[i],a[j]);
}
a[p]=a[j];
a[j]=x;
return j;
}
int random(int p,int r){//产生p~r间的一个随机数,必须r>p
int rd=rand()%(r-p+1);
return p+rd;
}
int randomizedPartion(int* a,int p,int r){//随机化的划分算法
int i=random(p,r);
swap(a[i],a[p]);
return partion(a,p,r);
}
int randomizedSelect(int* a,int p,int r,int k){//从数组a[p:r]中找第k小数
if(p==r) return a[p];
int i=0,m=0;
i=randomizedPartion(a,p,r);//i>=p
int j=i-p;//左边有j个元素(不包括i)
int l=0;
for(l=i;l<=r;l++) if(a[l]==a[i]) m++;//连续m个相同的元素
if(k<j) return randomizedSelect(a,p,i-1,k);
else if((k-j)<=m) return a[i];//0=<k-j<=m,则该k小数在m中
else return randomizedSelect(a,i+m,r,k-j-m);//k-j>m，从m开始找第k-j-m小数
}
void quickSort(int* a,int p,int r){//快速排序算法
if(p<r){
int q=randomizedPartion(a,p,r);
quickSort(a,p,q-1);
quickSort(a,q+1,r);
}
}
int ySteps(int* y,int n){//Y轴方向上移动的最优步数
int i=0,b[NUM];
for(i=0;i<n;i++) b[i]=y[i];
int m=n/2;//分割位置
int M=randomizedSelect(b,0,n-1,m);//水平分割线的位置，即中位数
int sum=0;
for (i=0;i<n;i++) {
sum+=abs(b[i]-M);
}
return sum;
}
int xSteps(int* x,int n){//X轴方向上的移动的最优步数
int i=0,b[NUM];
for(i=0;i<n;i++) b[i]=x[i];
quickSort(b,0,n-1);//对b进行排序
for(i=0;i<n;i++) b[i]=b[i]-i;
int m=n/2;
int K=randomizedSelect(b,0,n-1,m);//中位数
int sum=0;
for (i=0;i<n;i++) {
sum+=abs(b[i]-K);
}
return sum;
}
int main(){
int n=0;
int x[NUM],y[NUM];
memset(x,0,sizeof(x));
memset(y,0,sizeof(y));
scanf("%d",&n);
int i=0;
for (i=0;i<n;i++) scanf("%d%d",&x[i],&y[i]);
int a=xSteps(x,n);
int b=ySteps(y,n);
printf("%d\n",a+b);
return 0;
higer
2 2 1 3 3，按照书中的算法(P24)，得到的结果是：1 2 | 2 3 3，其中‘|’表示分割位置j，也就是说书中算法并没有将相等的元
素区分开，它只保证了左边部分数不大于a[j]，右边部分数不小于a[j]，这样有可能出现相等的数被分到了两边的情况，这虽然不会对“快排算法”的排
序结果造成影响，但会造成后面的第K小数选择的算法的死循环。具体问题看看下面书中的算法代码：
int partion(int* a,int p,int r){//快排算法中的分割函数
int i=p,j=r+1;
int x=a[p];
while (1==1) {
while(a[++i]<x&&i<r);//注意循环中的判断是a[++i]<x，因此等于x的元素会被分到右边
while(a[--j]>x);//注意循环中的判断是a[--j]>x，因此等于x的元素会分到左边
if(i>=j) break;
swap(a[i],a[j]);
}
a[p]=a[j];
a[j]=x;
return j;
}
为了使分割的情况更好，也就是说与分割点位置相等的元素我们应该分到一边去，而不是分布在两侧，fox example，例子：2 2 1 3 3 利
用书中算法的分割结果是1 2 | 2 3 3，修改算法我们希望得到的结果是：1 |2 2 3 3，即与2相等的元素都在右边，当然你分到左边也是
可以的。下面是在原算法基础上做的修改：
int partion(int* a,int p,int r){//快排算法中的分割函数
int i=p,j=r+1;
int x=a[p];
while (1==1) {
while(a[++i]<x&&i<r);//<x的元素都在左边
while(a[--j]>=x&&j>p);//>=x的元素都在右边，注意：当j减到p位置时，由于a[j]=a[p]，j继续减1，会导致无
效值，因此需要加一判断j>p，对于之前算法不用加此判断
if(i>=j) break;
swap(a[i],a[j]);
}
a[p]=a[j];
a[j]=x;
return j;
}
另外，分割函数虽然修改好了，但是对于第K小数选择算法依然会出现问题，该算法同样对相等数值的元素情况没作考虑，特别是在出现连续多个相等元素的情
况。书中原算法是这样的：
int randomizedSelect(int* a,int p,int r,int k){//从数组a[p:r]中找第k小数
if(p==r) return a[p];
int i=0;
i=randomizedPartion(a,p,r);
int j=i-p+1;//j个元素,包括i
if(k<=j) return randomizedSelect(a,p,i,k);
else return randomizedSelect(a,i+1,r,k-j);
}
对于序列1 2 2 3 3，分割后得到的可能结果是1 | 2 2 3 3，对于右半部分2 2 3 3，如果随机函数选择第一个作为分割点，那么每
次返回的i值都是一样的，都是第一个位置（对应这里的p，如果p是0，死循环就出现了），所以后面的分割是无效的，因此需要判断分割后从i位置开始有多
少个相同的元素，设元素个数为m，元素(不包括i)个数j=i-p,这样分割后会出现三种可能的情况：1）如果k<j，直接在左边找第k小元素；2）如
果k>=j并且k-j<=m，也就是说第k小元素存在于这m个相同的元素中；3）如果k-j>m，则第k小元素在m外，需要找a[i+m:r]中的第
k-j-m小元素。分析后得到的修改算法如下：
int randomizedSelect(int* a,int p,int r,int k){//从数组a[p:r]中找第k小数
if(p==r) return a[p];
int i=0,m=0;
i=randomizedPartion(a,p,r);//i>=p
int j=i-p;//左边有j个元素(不包括i)
int l=0;
for(l=i;l<=r;l++) if(a[l]==a[i]) m++;//连续m个相同的元素
if(k<j) return randomizedSelect(a,p,i-1,k);
else if((k-j)<=m) return a[i];//0=<k-j<=m,则该k小数在m中
else return randomizedSelect(a,i+m,r,k-j-m);//k-j>m，从m开始找第k-j-m小数
}
> ...
>
> read more »
Ziyu Yu
测试用例来说时间复杂度是O(n^2)?
higer 写道:
higer
第一组
5
3 1
3 2
3 4
3 3
3 5
第二组
5
1 2
2 2
4 2
5 2
第一组结果应该是14，第二组数据结果应该是：0
On Apr 21, 5:11 pm, 效云 李 <lixiaoyun...@gmail.com> wrote:
higer
Ziyu Yu
higer 写道:
Ziyu Yu
Ziyu Yu 写道: