我的解法
解题思路：直接循环加起来求和，顺时针求1-3和3-1两部分的和，然后比较！暴力求解，最后一个测试用例超时，只得了17分。
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
32
33
34
35
36
37
38
39
40
41
42
43
44
| #include <cstdio>
const int N=100010;
const int M=10010;
int D[N],n,m,x,y;
struct Node{
int x,y;
};
Node exits[M];
int getDist(int start,int end){
int sum=0,i=start;
while(i<=n){
sum+=D[i];
i++;
if(i>n){
i=i%n;
}
if(i==end) break;
}
return sum;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&D[i]);
}
scanf("%d",&m);
for(int i=0;i<m;i++){
scanf("%d %d",&x,&y);
exits[i].x=x;
exits[i].y=y;
}
for(int i=0;i<m;i++){
int a=getDist(exits[i].x,exits[i].y);
int b=getDist(exits[i].y,exits[i].x);
printf("%d\n",(a<b?a:b));
}
return 0;
}
|
算法笔记解法
解题思路：将位置1到后面每一个节点的距离和保存到一个数组，然后dis(left,right)=最右边的值到1的距离减去最左边的值到1的距离，最后将结果和用总和sum减去该结果，也就是逆循环的结果进行比较，得出最终结果！
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| #include <cstdio>
const int N=100010;
const int M=10010;
int n,m,sum=0,D[N],dis[N];
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&D[i]);
sum+=D[i];
dis[i+1]=sum;
}
scanf("%d",&m);
int left,right,temp;
for(int i=0;i<m;i++){
scanf("%d%d",&left,&right);
if(left>right) temp=dis[left]-dis[right];
else temp=dis[right]-dis[left];
printf("%d\n",temp<(sum-temp)?temp:(sum-temp));
}
return 0;
}
|