算法设计与分析 2.5 Joyvan的难题

★题目描述

Joyvan最近遇到了一个难题,对于一个包含
N个整数的序列a1,a2,……,aN，定义：f(i,j)=(j-i)2+(j∑k=i+1 ak)2
现在Joyvan想要你帮他计算所有
f(i,j)(1<=i<j<=N)的最小值。

★输入格式

输入的第一行为数字N，表示给定序列的长度。
第二行包含N个整数，表示序列中的整数a1,a2,……,aN。

★输出格式

输出一个整数，即所有f(i,j)(1<=i<j<=N)的最小值。

★样例输入

4
1 0 0 -1

★样例输出

1

★提示

网上找到的过10个点的代码

#include <iostream>

#define SQUARE(x) ((x)*(x))
using namespace std;

int main()
{
    int n;
    cin >> n;
    long total = 0;
    long sum[n+10];
    int tmp;
    for(int i=0; i<n; i++){
        scanf("%d", &tmp);
        total += tmp;
        sum[i] = total;
    }
    long minRes = 0x7ffffff;
    int i, j;
    for(i=0; i<n; i++){
        for(j=i+1; j<n; j++){
            if(SQUARE(j-i) > minRes){
                break;
            }
            minRes = min(SQUARE(j-i) + SQUARE(sum[j] - sum[i]), minRes);
        }
    }
    cout << minRes << endl;
    return 0;
}

下面是自己写的，用二分法，但是仅过8个点，最后两个测试点超时了

/*
对公式进行变形
假设 xi=i，yi= i∑k=1 ak
那么 f(i,j)=(xj-xi)2+(yj-yi)2
那么也就是相当于问距离最近的两点

现在的问题就是如何使用二分法找到距离最近的两点

可以百度“平面最近点对”，即可找到模板题 
*/
#include<bits/stdc++.h>
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
using namespace std;

int n;
int Y[100005]={0};

long Dist(int i, int j){
    return 1l*(i-j)*(i-j) + 1l*(Y[i]-Y[j])*(Y[i]-Y[j]);
}

long  df(int L, int R){
    if(L>=R) return 0x3ffff;
    if(L+1==R) return Dist(L,R);
    
    int mid = (L+R)>>1;
    long min_dist = min(df(L,mid), df(mid+1,R));
    
    int lim = sqrt(min_dist)+1;
    int sta = max(L, mid-lim), end=min(R, mid+lim);
    for(int i=sta; i<=end; ++i) for(int j=i+1; j<=end; ++j){
        min_dist = min(min_dist, Dist(i, j));
    }
    return min_dist;
}

int main(){
    int a;
    scanf("%d",&n);
    for(int i=1; i<=n; ++i){
        scanf("%d",&a);
        Y[i]=Y[i-1]+a;
    }

    cout<<df(1, n)<<endl;
    return 0;
} 

算法设计与分析 2.5 Joyvan的难题

原文：https://www.cnblogs.com/yejifeng/p/12053490.html