#12865. 找朋友(friend)

70分做法：不少人都得了70分，思路很简单，分两种情况讨论

1.编号小的到编号大的
2.编号大的到编号小的（因为小朋友们围成了一个圈）

70分代码：

#include<bits/stdc++.h>
using namespace std;    
int n,a[10005],sum=0;
void solve(){
    int xx,yy;
    cin>>xx>>yy;
    int x=min(xx,yy),y=max(xx,yy);
    int sum1=0,sum2=0;
    for(int i=x;i<y;i++){
        sum1+=a[i];
    }
    sum2=sum-sum1;
    sum1*=(y-x);
    x+=n;
    sum2*=(x-y);
    cout<<min(sum1,sum2)<<endl;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        sum+=a[i];
    }
    int k;
    cin>>k;
    while(k--){
        solve();
    }
    return 0;
}

但令人悲伤的是：

对于 100% 的数据， 满足 n<=10000, k<=1000000

而上面的做法复杂度为O(nk),妥妥的TLE！

所以我们需要对此进行优化

其中有k组数据所以要循环k次，这是不可以省略的

所以我们只能优化O（n）的循环

-------------------------------------------------分界线-------------------------------------------------------

此处强烈建议食用前缀和

先跳脱出小朋友围成一圈的情境

举个栗子：

编号  1  2  3  4  5

数值  10 20 30 40 50

题目中我们要求的是从一个编号到另一个编号数值之和

比如：

求编号3-5的数值之和

刚才我们用了循环累加法

需要耗费O（n）的复杂度

但是我们可以先将1-5的数值和算出来

再减去1-2的数值和

就能快速得出3-5的数值和了

不信？验算一下：

1-5：10+20+30+40+50=150

1-2：10+20=30

3-5：30+40+50=120

而150-30=120

所以可以得出规律：

x-y的数值和=1-y之和减去1-（x-1）的和

这样只需要在输入时每次统计一边=遍前缀和（即这个位置到第一个位置的权值和）

每次计算使用即可，一劳永逸！

注意点：

1.输入的x和y不一定有序，需要手动确保有序

2.开long long + printf + scanf

3.x,y在计算前都要-1

AC主代码：

long long sum1=(dis[y]-dis[x])*(y-x);
long long sum2=(dis[n]-dis[y]+dis[x])*(x+n-y);