士兵站隊(duì)問題題解

《士兵站隊(duì)問題題解》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

1、【問題描述】在一個(gè)劃分成網(wǎng)格的操場(chǎng)上，n個(gè)士兵散亂地站在網(wǎng)格點(diǎn)上。網(wǎng)格點(diǎn)用整數(shù)坐標(biāo)(x,y)表示。士兵們可以沿網(wǎng)格邊往上、下、左、右移動(dòng)一步，但在同一時(shí)刻任一網(wǎng)格點(diǎn)上只能有一名士兵。按照軍官的命令，士兵們要整齊地列成一個(gè)水平隊(duì)列，即排列成(x,y),(x+1,y),…,(x+n-1,y)。如何選擇x和y的值才能使士兵們以最少的總移動(dòng)步數(shù)排成一行。編程計(jì)算使所有士兵排成一行需要的最少移動(dòng)步數(shù)。【輸入格式】第1行是士兵數(shù)n，1≤n≤10000。接下來n行是士兵的初始位置，每行有2個(gè)整數(shù)x和y，-10000≤x，y≤10000?！据敵龈袷健恳粋€(gè)數(shù)據(jù)，即士兵排成一行需要的最少移動(dòng)步數(shù)?！据?/p>

2、入樣例】sol.in51222133-233【輸出樣例】sol.out8?分析：一士兵有多種移動(dòng)方式通過適當(dāng)?shù)囊苿?dòng)順序和移動(dòng)路線可以使得同一時(shí)刻不會(huì)有兩名士兵站在同一點(diǎn)二題目要求最佳移動(dòng)方式（即求移動(dòng)的最少步數(shù)）題目要求轉(zhuǎn)化為求士兵站立的“最終位置”，即如何取“最終位置”使得士兵移動(dòng)的步數(shù)最少（最優(yōu)）Y軸方向上的考慮設(shè)目標(biāo)坐標(biāo)為M，即n個(gè)士兵最終需要移動(dòng)到的Y軸的坐標(biāo)值為Mn個(gè)士兵的Y軸坐標(biāo)分別為：Y0，Y1，Y2…………Yn-1則最優(yōu)步數(shù)S=

3、Y0-M

4、+

5、Y1-M

6、+

7、Y2-M

8、+…………+

9、Yn-1-M

10、結(jié)論：M取中間點(diǎn)的值使得S為最少（最優(yōu)）證明：……從最上和最下的兩個(gè)士兵

11、開始遞推……最優(yōu)位置最優(yōu)位置歸結(jié)到最后，處于中間位置的士兵的Y軸坐標(biāo)值就是“最終位置”的Y軸坐標(biāo)可能有兩種情況士兵總數(shù)為雙數(shù)情況：取中間兩點(diǎn)間的任意一個(gè)位置士兵總數(shù)為單數(shù)情況：取中間點(diǎn)的所在位置解決辦法：對(duì)所有的Y軸坐標(biāo)進(jìn)行排序（O（nlogn））或者進(jìn)行線性時(shí)間選擇（O（n））然后取“中間”點(diǎn)的Y軸坐標(biāo)值作為最佳位置M的值最后通過公式求出Y軸方向上移動(dòng)的最優(yōu)步數(shù)X軸方向上的考慮首先需要對(duì)所有士兵的X軸坐標(biāo)值進(jìn)行排序然后，按從左至右的順序依次移動(dòng)到每個(gè)士兵所對(duì)應(yīng)的“最終位置”（最優(yōu)），所移動(dòng)的步數(shù)總和就是X軸方向上需要移動(dòng)的步數(shù)例，最左的士兵移動(dòng)到“最終位置”的最左那位，第二個(gè)士兵

12、移動(dòng)到“最終位置”的第二位則總的步數(shù)為：士兵一移動(dòng)步數(shù)+士兵二移動(dòng)步數(shù)+……+士兵n移動(dòng)步數(shù)如何確定X軸方向上的最佳的“最終位置”？共n個(gè)士兵他們相應(yīng)的X軸坐標(biāo)為：X0，X1，X2…………Xn-1設(shè)，士兵需要移動(dòng)到的“最終位置”的X軸坐標(biāo)值為：k，k+1，k+2…………k+（n-1）則所求最優(yōu)步數(shù)S=

13、X0-k

14、+

15、X1-（k+1）

16、+

17、X2-（k+2）

18、+……+

19、Xn-1-（k+（n-1））

20、經(jīng)過變形S=

21、X0-k

22、+

23、（X1-1）-k

24、+

25、（X2-2）-k

26、+…………+

27、（Xn-1-（n-1））-k

28、注意到公式的形式與Y軸方向上的考慮一樣，同樣是n個(gè)已知數(shù)分別減去一個(gè)待定數(shù)后取

29、絕對(duì)值，然后求和因此還是采用取中位數(shù)的辦法求得k值，最后算出最優(yōu)解。?參考程序：type?arr=array[-10001..10001]oflongint;var?i,j,k,l,n,m,num:longint;?f:array[-10001..10001]ofboolean;?a,b,c:arr;procedure?ok(l,r:longint);?var?i,j,x,y:longint;begin?i:=l;j:=r;x:=a[(l+r)div2];?repeat???whilea[i]

30、en??begin?????y:=a[i];a[i]:=a[j];a[j]:=y;?????i:=i+1;j:=j-1;???end;?untili>j;?ifl

31、b[j]:=y;?????i:=i+1;j:=j-1;???end;?untili>j;?ifl