【HihoCoder - 1880】地铁环线 （前缀和，水题，模拟）

题干：

H市有一环线地铁，一共包含N站，编号1~N。正向行驶的地铁会按1 -> 2 -> 3 -> ... -> N -> 1的方向行驶，反向会按1 -> N -> N-1 -> ... -> 3 -> 2 -> 1的方向行驶。  

给定所有相邻两站之间地铁行驶的时间(正向、反向时间相同），假设小Hi要从第X站到第Y站，请你判断是小Hi是乘坐正向还是反向的列车用时更少？

Input

第一行包含两个整数N和M，分别代表地铁站数目和询问的次数。

第二行包含N个整数A1, A2, ... AN，其中Ai代表从第i站正向行驶到下一站所用的时间。  

以下M行每行包含两个整数X和Y，代表一个询问。

1 ≤ N, M ≤ 100000  1 ≤ X, Y ≤ N  1 ≤ Ai ≤ 100000

Output

对于每组询问，输出一个整数表示最短时间。

Sample Input

5 2
1 2 3 4 5  
1 3  
1 5

Sample Output

3  
5

解题报告：

   相当于一个循环队列就可以了、、、

AC代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define ll long long
#define pb push_back
#define pm make_pair
#define fi first
#define se second
using namespace std;
const int MAX = 2e5 + 5;
ll a[MAX];
ll sum[MAX];
int main()
{
	int n,m;
	cin>>n>>m;
	for(int i = 1; i<=n; i++) scanf("%lld",a+i),sum[i] = sum[i-1] + a[i]; 
	
	while(m--) {
		int l,r;
		scanf("%d%d",&l,&r);
		if(r < l) swap(l,r);
		ll tmp1 = sum[r-1] - sum[l-1];
		ll tmp2 = sum[n] - sum[r-1] + sum[l-1];
		printf("%lldn",min(tmp1,tmp2));
	}
	
	
	return 0 ;
 }

最后

以上就是自信马里奥为你收集整理的【HihoCoder - 1880】地铁环线 （前缀和，水题，模拟）的全部内容，希望文章能够帮你解决【HihoCoder - 1880】地铁环线 （前缀和，水题，模拟）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。