一、可借鉴的

1. 超时原因

这道题的测试点三一直超时，原因是我的方法复杂度是O(n^2)，而算法笔记上的解法只有O(n)

2. 使用algorithm库

swap()和min()

3. 一行内输入数据仍按原方法

二、代码

题目：https://pintia.cn/problem-sets/994805342720868352/problems/994805435700199424

1. 算法笔记‘s

优化的地方是提前计算出1到各个点的距离（dist数组），要求某两点的距离则让其相减即可

  2. #include<cstdio>
  3. #include<algorithm>
  4. using namespace std;
  6. const int MAXN = 100005;
  7. int dis[MAXN],A[MAXN];//dis存放顺时针方向的距离，A存放i到i+1的距离
  8. int main(){
  9.     int sum = 0,query,n,left,right;
  10.     scanf("%d",&n);
  11.     for(int i = 1;i <= n;i++)
  12.     {
  13.         scanf("%d",&A[i]);
  14.         sum += A[i];
  15.         dis[i] = sum;
  16.     }
  17.     scanf("%d",&query);
  18.     for (int i = 0;i<query;i++)
  19.     {
  20.         scanf("%d%d",&left,&right);
  21.         if(left>right) swap(left,right);
  22.         int temp = dis[right-1] - dis[left-1];
  23.         printf("%d\n",min(temp,sum - temp));
  24.     }
  25.     return 0;
  26. }

2. 俺写的

#include<cstdio>

int main(){
    int N = 0,M = 0;
    int A = 0,B = 0;
    int sum1 = 0,sum2 = 0;
    int dist[100000] = {0};
    scanf("%d",&N);
    for(int i = 1;i <= N;i++)
    {
        scanf("%d",&dist[i]);
    }
    //printf("N是%d\n",N);
    scanf("%d",&M);
    for(int i = 1;i <= M;i++)
    {
        //printf("dist[%d] = %d\n",i,dist[i]);
        scanf("%d %d",&A,&B);
        int k1 = A,k2 = B;
        int sum1 = 0,sum2 = 0;
        while(k1!=B)
        {
            sum1 = dist[k1] + sum1;
            k1 = k1%N+1;
        }

        while(k2!=A)
        {
            sum2 = dist[k2] + sum2;
            k2 = k2%N+1;
        }
        printf("%d",sum1<sum2?sum1:sum2);
        if (i!=M){printf("\n");}
    }
    return 0;
}