PAT 1046 Shortest Distance
#include<stdio.h> int main(){ int n,m,i,j,d[100000]; scanf("%d", &n); for(i=1;i<=n;i++){ scanf("%d", &d[i]); } scanf("%d", &m); int start,end,temp,sum1,sum2; for(j=0;j<m;j++){ scanf("%d %d", &start, &end); sum1 = sum2 = 0; temp = start; while(temp != end){ sum1 += d[temp]; temp++; if(temp>n) temp = 1; } temp = start; while(temp != end){ if(temp==1) temp = n+1; sum2 += d[--temp]; } if(sum1 <= sum2){ printf("%d\n", sum1); }else { printf("%d\n", sum2); } } return 0; }
运行超时。
#include<stdio.h> int main(){ int n,m,i,j,d[100001],total=0,temp; scanf("%d", &n); //每个点存储的都是D1到该点的距离总和,D1存储环的总和 for(i=1;i<=n;i++){ scanf("%d", &temp); total += temp; d[i+1] = total; } d[1] = total; scanf("%d", &m); int start,end,t,sum1,sum2; for(j=0;j<m;j++){ scanf("%d %d", &start, &end); if(start > end){ t = start; start = end; end = t; } if(start == 1){ sum1 = d[end]; sum2 = d[1] - sum1; }else { sum1 = d[end] - d[start]; sum2 = d[1] - sum1; } if(sum1 <= sum2){ printf("%d\n", sum1); } else { printf("%d\n", sum2); } } return 0; }
正常。