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("%lldn",ans); } return 0; }
文章来源: 博客园
- 还没有人评论,欢迎说说您的想法!