【题目链接】:http://codeforces.com/problemset/problem/429/D

【题意】



给你n个数字;

让你求出一段区间[l,r]

使得

(r−l)2+(∑rl+1a[i])2最小

【题解】



求出前缀和数组sum[i];

可以发现,如果把数组的下标i作为第一维坐标(x),前缀和sum[i]作为第二维坐标(y);

所求的式子就是任意两点之间的距离平方;

问题转化成:已知平面上的n个点;

求最近的两个点之间的距离的平方;

这个可以用分治的方法搞出来;

(感觉就是个剪枝的暴力);

据说复杂度是N⋅log2N



【Number Of WA】



2



【完整代码】

#include <bits/stdc++.h>

using namespace std;

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define LL long long

#define rep1(i,a,b) for (int i = a;i <= b;i++)

#define rep2(i,a,b) for (int i = a;i >= b;i--)

#define mp make_pair

#define pb push_back

#define fi first

#define se second

#define ms(x,y) memset(x,y,sizeof x)

#define Open() freopen("F:\\rush.txt","r",stdin)

#define Close() ios::sync_with_stdio(0),cin.tie(0)

typedef pair<int,int> pii;

typedef pair<LL,LL> pll;

const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};

const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};

const double pi = acos(-1.0);

const int N = 1e5+100;

const LL INF = 8e18 + 1;

//4e18

//8e18

struct abc{

    LL x,y;

};

LL a[N],sum[N];

abc b[N],c[N];

int n;

LL sqr(LL x){

    return x*x;

}

LL dis(abc a,abc b){

    LL temp = 0;

    temp += sqr(a.x-b.x);

    temp += sqr(a.y-b.y);

    return temp;

}

LL query(int l,int r){

    LL ret = INF;

    if (l>=r) return ret;

    if (l+1==r) return dis(b[l],b[r]);

    int m = (l+r)>>1,k = 0;

    LL t1 = query(l,m),t2 = query(m+1,r),temp;

    ret = min(t1,t2);

    rep2(i,m,l){

        temp = sqr(b[i].x-b[m].x);

        if (temp>ret) break;

        c[++k] = b[i];

    }

    rep1(i,m+1,r){

        temp = sqr(b[i].x-b[m].x);

        if (temp>ret) break;

        c[++k] = b[i];

    }

    sort(c+1,c+1+k,[&] (abc a,abc b) {return a.y<b.y;});

    rep1(i,1,k)

        rep1(j,i+1,k){

            temp = sqr(c[j].y-c[i].y);

            if (temp > ret) break;

            ret = min(ret,dis(c[i],c[j]));

        }

    return ret;

}

int main(){

    //Open();

    Close();

    cin >> n;

    rep1(i,1,n) cin >> a[i];

    rep1(i,1,n) sum[i] = sum[i-1] + a[i];

    rep1(i,1,n){

        b[i].x = i,b[i].y = sum[i];

    }

    sort(b+1,b+1+n,[&] (abc a,abc b) { return a.x < b.x;});

    cout << query(1,n) << endl;

    return 0;

}