2353 排隊問題
1.0 秒 131,072.0 KB 20 分 初學者3級題
n個身高不同的小朋友，分別站在編號1-n的格子里，n個格子排成1列。現(xiàn)在我們希望他們能夠按照身高的順序從低到高排成1列。按現(xiàn)在的順序給出n個小朋友的身高，問所有小朋友總共需要移動多少個格子，才能按照身高從低到高的順序排好隊。注：從格子3移動到格子1，需要移動2個格子。

例如：4個小朋友，身高分別是：

1220 1210 1200 1250

按照身高順序拍好后，應該是：

1200 1210 1220 1250，身高1200的小朋友需要移動2格，身高1210和1250的小朋友，不需要移動，身高1220的小朋友需要移動2格，4個小朋友總共需要移動2 + 2 = 4格。

輸入
第一行：一個數(shù)n(1<=n<=10000)。
后面n行：每行1個數(shù)，表示小朋友的身高。
輸出
輸出所有小朋友移動距離之和。
輸入樣例
4
1220
1210
1200
1250
輸出樣例
4
分析
采用兩個數(shù)組，一個數(shù)組a存儲輸入值，一個數(shù)組b存儲排序后的值
兩數(shù)組中的坐標差即為每位小朋友的移動距離，這里需要在b數(shù)組中查找a中數(shù)據(jù)的位置。
排序使用sort函數(shù)
二分查找使用lower_bound()函數(shù)

AC代碼
下面代碼中數(shù)組從1開始存儲，因此這里sort函數(shù)從b[1]開始排序：sort(b+1,b+n+1)因為數(shù)組中b[0]沒存放東西，從b[1]開始存放。
同樣的道理,lower_bound()函數(shù)也是從b[1]開始查找：lower_bound(b+1,b+1+n,a[i])-b后面-b是減去數(shù)組首地址.

如果

#include<iostream> #include<cmath> #include<algorithm> using namespace std;int a[10001],b[10001],n,dis=0;int main(){cin>>n;for(int i=1;i<=n;i++){cin>>a[i];b[i]=a[i];}sort(b+1,b+n+1);for(int i=1;i<=n;i++){int pos=lower_bound(b+1,b+n+1,a[i])-b;// cout<<pos<<endl;dis+=abs(pos-i);}cout<<dis<<endl; }

補充知識
sort()
Sort函數(shù)有三個參數(shù):

（1）第一個是要排序的數(shù)組的起始地址。

（2）第二個是最后一位要排序地址的下一位（也就是左閉右開區(qū)間的由來）

（3）第三個參數(shù)是排序的方法，默認的排序方法是從小到大排序。
比如

sort(a,a+n);//對數(shù)組a進行排序，數(shù)組長度為n，a+n表示最后一個元素的下一個位置

lower_bound()
lower_bound( begin,end,num ):從數(shù)組的begin位置到end-1位置二分查找第一個小于或等于num的數(shù)字，找到返回該數(shù)字的地址，不存在則返回end。通過返回的地址減去起始地址begin,得到找到數(shù)字在數(shù)組中的下標。注意區(qū)間左閉右開。

總結

以上是生活随笔為你收集整理的51Nod2353 排队问题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。