PAT甲级-1046 Shortest Distance (20分)

点击链接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

Sample Output:

3
10
7

题意：
输入连续的一串数，下表从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<bits/stdc++.h>
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;
}