PAT 1046

题目 ： Shortest Distance

分值 ： 20
难度 ： 简单题
思路 ： 两个值取个小的就ok了
坑点 ： 每次加和会超时
评语 ： 数组加和优化

具体代码如下

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
27
28
29
30
31
#include <iostream>
using namespace std;
int total ;
int data[100001];
int main() {
    int N ;
    cin >> N ;
    int temp ;
    data[0] = 0 ;
    for(int i = 1 ; i<=N ; i++)
    {
        scanf("%d",&temp);
        total += temp ;
        data[i] = total  ;
    }
    int M ;
    cin>> M ;
    int c1 ,c2 ;
    for(int i = 0 ; i< M; i++)
    {
        scanf("%d%d",&c1,&c2) ;
        //cin >>c1 >>c2 ;
        int sum = 0 ;
        int s = c1>c2 ? c2 :c1 ;
        int e = c1>c2 ? c1 :c2 ;
        sum = data[e-1] -data[s-1 ] ;
        int min = sum > total-sum ?  total-sum : sum ;
        printf("%d\n",min) ;
        //cout << min  <<endl ;
    }
}