点击链接PAT甲级-AC全解汇总

题目：
The task is really simple: given N exits on a highway which forms a simple cycle, you are supposed to tell the shortest distance between any pair of exits.

Input Specification:
Each input file contains one test case. For each case, the first line contains an integer N (in [3,10^​5​​ ]), followed by N integer distances D_​1​​ D_​2​​ ⋯ D_​N​​ , where D_​i​​ is the distance between the i-th and the (i+1)-st exits, and D_​N​​ is between the N-th and the 1st exits. All the numbers in a line are separated by a space. The second line gives a positive integer M (≤10^​4​​ ), with M lines follow, each contains a pair of exit numbers, provided that the exits are numbered from 1 to N. It is guaranteed that the total round trip distance is no more than 10^​7​​ .

Output Specification:
For each test case, print your results in M lines, each contains the shortest distance between the corresponding given pair of exits.

Sample Input:

5 1 2 4 14 9
3
1 3
2 5
4 1
1
2
3
4
5

Sample Output:

3
10
7
1
2
3

题意：
输入连续的一串数，下表从1开始，再给出任意两个数的下标a,b，求：
min（[a,b)的和，[0,a)+[b,N]的和）

我的思路：
直接求和case2会超时，所以用个dis求从0开始到此的距离，因为：
[a,b)=[0,b)-[0,a)

求[0,a)+[b,N]也不用直接算，用所有数的和 - [a,b)即可

我的代码：

#include
using namespace std;

int main(){
    int N,M;
    cin>>N;
    int dis[N+1]={0},sum=0;
    for(int i=1;i<=N;i++)
    {
        int t;
        cin>>t;
        sum+=t;
        dis[i]=sum;
    }
    cin>>M;
    for(int i=0;i<M;i++)
    {
        int a,b;
        cin>>a>>b;
        int plan=abs(dis[a-1]-dis[b-1]);
        plan=min(plan,sum-plan);
        cout<<plan<<endl;
    }
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26