题意
有n个车站排成一个环形,给定n个车站之间的距离,求从第s个车站到第t个车站所需的最短距离。
输入格式
第一行给定车站个数n。
第二行给定n个车站之间的距离,其中第i个数表示第i个车站到第i+1个车站的距离d_{i}。特别地,最后一个数表示第一个车站与最后一个车站之间的距离。
第三行给定两个整数s和t,表示起点和终点。
输出格式
输出共一行,表示第s个车站到第t个车站之间的最短距离。
题解
注意题目说了车站是围成一个环形的!
所以有两种走法(不然直接暴力、前缀和、线段树、树状数组求区间和),一种是从s走到t,还有一种是反着走(废话)。
为了方便计算,如果输入的s\gt{t},那么就交换s和t,保证s\leq{t}.
注: 本文代码使用的交换方法是用的位运算,只不过快一点,其实跟普通的方法是一样的。
然后其实会发现此时s车站到t车站的距离有两种:
正着走,就是s到t的区间和
反着走,其实反过来想,就等于总路程长度(1~n)减去1情况下的s到t的区间和
那么接下来只要比较一下谁小就可以了。
代码
#include<stdio.h>
int n,d[110],s,t,sum,dis;
int main()
{
scanf("%d",&n);
for(register int i=1;i<=n;++i)
{
scanf("%d",&d[i]); //输入路程
sum+=d[i]; //求总路程
}
scanf("%d%d",&s,&t);
if(s>t) //如果s>t就交换s和t
{
s^=t; //使用的是位运算交换的
t^=s; //只是快一点
s^=t; //如果不会的(不存在的)大佬们可以就用朴素的方法
}
for(register int i=s;i<t;++i) dis+=d[i]; //求区间和,注意题目描述,此时的约束条件为i<t而不是i<=t
printf("%d\n",dis<sum-dis? dis:sum-dis); //比较1情况和2情况的距离,输出短的距离
return 0;
}