题意有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; }

洛谷CF278A题解

damage

题意

有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;
}