2.1 序列求解

发表于 | 更新于 | 分类于 | 阅读次数：

实验任务

对于一个包含 \(n\) 个整数的序列 \(a_1, a_2, \cdots, a_n\)。定义：

\[f(i,j)=(j-i)^2+(\sum _{k=i+1}^{j}{\alpha{_k}})^2.\] 现要求计算出所有\(f(i,j)\ (1\leq i < j \leq n)\)中的最小值。

数据输入

输入的第一行为数字 \(n\ (2\leq n\leq 10^5)\)，表示给定序列的长度。第二行包含 \(n\) 个整数，表示序列中的整数 \(a_1, a_2, \cdots, a_n\ (|a_i|\leq 10^4)\)。

数据输出

输出一个整数，即对于所有\(f(i,j)\ (1\leq i < j \leq n)\) 中的最小值。

输入示例 输出示例
4
1 0 0 -1		 1

数据范围

\(80\%\)的得分点，\(n \leq 1000\)；\(20\%\)的得分点，\(n \leq 100000\)。

源代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <stdio.h>
#include <algorithm>
typedef __int64 ll;
const int N = 100005;
const ll inf = ll(9e18);
struct P{
    int x, y;
}p[N], tmp[N];
int cmpY(const P&a, const P&b){ return a.y<b.y; }
inline ll square(ll x){ return x*x; }
inline ll min(ll x, ll y){ return x<y ? x : y; }

ll Cpair(int left, int right){
    if (left == right) return inf;
    //x轴使用下标，数据本身已经平均分布了，无需考虑左右子集不平衡问题
    int m = (left + right) >> 1;
    int Xm = p[m].x;
    ll lim = min(Cpair(left, m), Cpair(m + 1, right));
    //递归返回的时候两个子段已经有序，合并时间为O(n)，注意稳定排序重载运算符会报错。
    std::inplace_merge(p + left, p + m + 1, p + right + 1, cmpY);
    int i, j, counter = 0;
    for (i = left; i <= right; ++i)
        if (square(p[i].x - Xm) <= lim)
            tmp[counter++] = p[i];//x坐标差不超过±d的所有点
    for (i = 0; i < counter; ++i) {
        for (j = i + 1; j < counter; ++j) {
            //y坐标差不超过±d的所有点，注意到y本身已经有序
            if (square(tmp[j].y - tmp[i].y) >= lim) break;
            ll disq = square(tmp[j].x - tmp[i].x) + square(tmp[j].y - tmp[i].y);
            lim = min(lim, disq);
        }
    }
    return lim;
}

int main(){
    int n, sum, a, i;
    scanf("%d", &n);
    for (i = 1; i <= n; ++i){
        scanf("%d", &a);
        sum += a;
        p[i].x = i, p[i].y = sum;
    }
    printf("%d\n", (int)Cpair(1, n));
    return 0;
}

设计思路与复杂度分析

令前缀和（可以预处理出来）\(sum_i=\sum_{j=1}^{i}{\alpha{_j}}\)，则\(f(i,j)=(j-i)^2+(sum_j-sum_i)^2\)。令二维平面上的点\(p_i = (i,sum_i)\)，则\(f(i,j) = (distance(i,j))^2\)。目标函数为\(\min f(i,j)= \min (distance(i,j))^2\)，即将问题转化为二维平面的最近点对问题。关于最近点对的知识点请参考教材P29。

算法耗时最多在归并排序（平衡），复杂度为\(O(nlogn)\)。

0%