士兵站隊問題

2019-11-08 01:56:34

字體：大中小

來源：轉載

供稿：網友

問題描述 N戰士的土地網格隨機散布在全國各地。 Gridland中的位置由一對（x，y）整數坐標給出。士兵可以移動 - 在一個移動中，一個士兵可以向上，向下，向左或向右移動一個單位（因此，他可以將他的x或他的y坐標改變1或-1）。士兵想要進入彼此相鄰的水平線（使得它們的最終位置是（x，y），（x + 1，y），…，（x + N-1，y） x和y）。整數x和y，以及士兵沿水平線的最終順序是任意的。目標是最小化所有士兵的行動總數，使他們進入這種配置。兩個或更多的士兵絕不能同時占據同一個位置。

問題分析 本題實質就是求 X 和 Y 方向總共需要移動的最少步數。假設n 個士兵的坐標分別為（X1,Y1）,(X2,Y2),(X3,Y3)……（Xn-1,Yn-1),(Xn,Yn)。對于 Y 方向來說，假如最后所有士兵都在y坐標為Y的坐標上，則即使求|Y1-Y|+|Y2-Y|+|Y3-Y|+……|Yn-1-Y|+|Yn-Y|的最小值，可以用數學方法證明 Y 值即是Y1，Y2，Y3……Yn-1,Yn的中位數，據此可以求出在Y方向需要移動的總步數；對于X方向，先對所有的X坐標從小到大排序，排序后，為了放便描述，我們依然用X1，X2，X3……Xn-1，Xn代表士兵排序后的位置，假如最后所有士兵站的位置為X，X+1，X+2……X+n-1，那么即是求|X1-X|+|X2-(X+1)|+|X3-(X+2)|+……|Xn-(X+n-1)|的最小值，即|X1-X|+|（X2-1）-X|+|（X3-2）-X|+……|（Xn-（n-1））-X|，X即為X1,X2-1,X3-2……Xn-(n-1)的中位數，據此可以求得X方向的最小移動步數。 代碼如下：

#include<iostream> #include<cstdlib> #include<cmath> #include<ctime> using namespace std; int partition(int *a,int low,int high){ int key = a[low]; while(low<high){ while(low < high&&a[high] >= key)high--; a[low] = a[high]; while(low<high&&a[low] <= key)low++; a[high]=a[low]; } a[low]=key; return low; } int RandomizedPartition(int *a,int low,int high){ srand((unsigned int)time(NULL)); int i = rand()%(high-low+1)+low; int temp; temp = a[i]; a[i] = a[low]; a[low] = temp; return partition(a,low,high); } int RandomizedSelect(int *a,int p,int r,int k){ if(p == r) return a[p]; int i=RandomizedPartition(a,p,r); int j=i-p+1; if(j==k) return a[i]; else if(j > k) return RandomizedSelect(a,p,i-1,k); else return RandomizedSelect(a,i+1,r,k-j); } void Qsort(int *a,int low,int high){ int key; if(low<high){ key = RandomizedPartition(a,low,high); Qsort(a,low,key-1); Qsort(a,key+1,high); } } int main(){ int x[10000],y[10000],n,xkey,ykey,x1[10000],sum; while(cin>>n){ sum = 0; for(int i =0;i < n;i ++) cin>>x[i]>>y[i]; Qsort(x,0,n-1); for(int i = 0;i < n;i++) x1[i] = x[i]-i; ykey=RandomizedSelect(y,0,n-1,(n+1)/2); xkey=RandomizedSelect(x1,0,n-1,(n+1)/2); for(int i = 0;i < n;i ++) { sum += abs(y[i]-ykey); sum += abs(x1[i]-xkey); } cout<<sum<<endl; } system("pause"); }

運行結果：