題干：

H市有一環(huán)線(xiàn)地鐵，一共包含N站，編號(hào)1~N。正向行駛的地鐵會(huì)按1 -> 2 -> 3 -> ... -> N -> 1的方向行駛，反向會(huì)按1 -> N -> N-1 -> ... -> 3 -> 2 -> 1的方向行駛。 ?

給定所有相鄰兩站之間地鐵行駛的時(shí)間(正向、反向時(shí)間相同），假設(shè)小Hi要從第X站到第Y站，請(qǐng)你判斷是小Hi是乘坐正向還是反向的列車(chē)用時(shí)更少？

Input

第一行包含兩個(gè)整數(shù)N和M，分別代表地鐵站數(shù)目和詢(xún)問(wèn)的次數(shù)。

第二行包含N個(gè)整數(shù)A1, A2, ... AN，其中Ai代表從第i站正向行駛到下一站所用的時(shí)間。 ?

以下M行每行包含兩個(gè)整數(shù)X和Y，代表一個(gè)詢(xún)問(wèn)。

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

Output

對(duì)于每組詢(xún)問(wèn)，輸出一個(gè)整數(shù)表示最短時(shí)間。

Sample Input

5 2 1 2 3 4 5 1 3 1 5

Sample Output

3 5

?

解題報(bào)告：

? ?相當(dāng)于一個(gè)循環(huán)隊(duì)列就可以了、、、

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("%lld\n",min(tmp1,tmp2));}return 0 ;}

?

總結(jié)

以上是生活随笔為你收集整理的【HihoCoder - 1880】地铁环线 （前缀和，水题，模拟）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。