1003 Express Mail Taking
問題描述：
除了傳統的課程，小火山還需要學習如何取快遞郵件，
快遞通常存放在柜子里，在小火山的學校，有一排n個柜子，從1到n，相鄰的兩個柜子之間的距離是1，入口在第一個柜子處，在這n個柜子中，第k個柜子比較特殊，它用于輸入口令打開其他柜門，
小火山有m個快遞要取，第i個快遞在柜子ai中，兩個快遞不會放在同一個柜子里，且k柜中沒有快遞，
為了防止快遞被盜，小火山不得不從入口開始一個一個地取走這些快遞，一般來說，如果他要取走快遞i,他必須先走到k柜輸入口令，然后再走到對應的柜字ai，當拿完最后一個快遞后，從入口處離開，
有很多快遞要取，所以小火山想找到步行的最小距離，
輸入：
第一行包含一個整數T(1 <T< 100)，即測驗用例的數量
對于每個測驗用例，第一行包含三個整數n，m，k(1 <k<n< 106，1 <m<min(n, 106)
下一行包含m個整數，即m個快遞分別在那個柜子里，第i個代表a:(1<ai<n，ai≠k)，（用容易理解的話表達了）
輸入保證∑m<2x106
**注意：由于輸入量大，最好使用scanf而不是cin，*
輸出：
對于每個測驗用例，輸出一行包含一個整數，表示最小步行距離，
題目大意：
有n個保險柜，編號為1~n，每兩個相鄰編號的柜子之間的距離為1，第k個保險柜用來打開其他柜子（每次只能同時打開一個保險柜），
從1出發，需要從m個保險柜中取東西后再從1離開，問距離最短的路線長度，
思路：
***注意理解題意，并不是到達k柜輸入口令后就可以依次取出所有快遞，而是每取走一個快遞就需要回傳k柜解鎖下一個柜子，***
只有在k柜和入口之間 且 離入口最近的快遞對最小步行距離有幫助，因為此快遞無需折回傳k柜，取走后直接到入口，（該距離不算入總距離，回傳入口路上已覆寫此距離了）
除此之外剩下的每個柜子i，所需步行距離都是2*abs(i-k)，再加入口到達k柜折返的距離2*(k-1)，即答案，
參考代碼：
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn=2000005;
int a[maxn];
int main()
{
int i,T,n,m,k,num;
ll ans;
scanf("%d",&T);
while (T--)
{
scanf("%d%d%d",&n,&m,&k);
ans=2ll*(k-1); //入口和k之間折返距離
num=k;
for (i=1;i<=m;i++)
{
scanf("%d",&a[i]);
ans+=2ll*abs(a[i]-k);
if (a[i]<num) num=a[i]; //找到離入口最近且在入口和k柜之間的快遞
}
if (num!=k) ans-=2ll*abs(num-k); //總距離減去重復的距離
printf("%lld\n",ans);
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/104999.html
標籤：其他
上一篇：米8黑磚了怎么救啊 沒有底層檔案