Blackops

初心易得，始终难守

0%

牛客练习赛11 E 求最值（差分+分治求最近点对）

发表于 分类于 ，

链接：https://www.nowcoder.com/acm/contest/59/E
来源：牛客网

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld

题目描述
给你一个长为n的序列a
定义f(i,j)=(i-j)2+g(i,j)2
g是这样的一个函数
pic
求最小的f(i,j)的值，i!=j

输入描述:
第一行一个数n
之后一行n个数表示序列a
输出描述:
输出一行一个数表示答案
示例1
输入

4
1 0 0 -1
输出

1
备注:
对于100%的数据，2 <= n <= 100000 , |ai| <= 10000

题目链接：E.求最值
观察式子可以发现第二项$\sum_{l+1}^{r}{a_i}$=$presum[r]-presum[l]$，那么这个式子实际上是求二维点集${(i, presum[i])}$中的最近点距离，然后就很模板地分治求一下就可以了，题目数据比较水，$O(N^2)$的算法稍微优化优化一下也可以过，筛点的时候忘记开平方$TLE$到结束（真菜……）
代码：

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define CLR(x,y) memset(x,y,sizeof(x))
#define LC(x) (x<<1)
#define RC(x) ((x<<1)+1)
#define MID(x,y) ((x+y)>>1)
typedef pair<int, int> pii;
typedef long long LL;
const double PI = acos(-1.0);
const int N = 100010;
struct Point
{
    LL x, y;
} p[N], temp[N];

inline LL sqr(LL x)
{
    return x * x;
}
inline LL dis(const Point &a, const Point &b)
{
    return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}
inline bool cmpx(const Point &a, const Point &b)
{
    return a.x < b.x;
}
inline bool cmpy(const Point &a, const Point &b)
{
    return a.y < b.y;
}
LL solve(int l, int r)
{
    int len = r - l + 1;
    if (len <= 1)
        return 0x3f3f3f3f3f3f3f3f;
    if (len == 2)
        return dis(p[l], p[r]);
    if (len == 3)
        return min({dis(p[l], p[r - 1]), dis(p[l], p[r]), dis(p[l + 1], p[r])});
    else
    {
        int mid = MID(l, r);
        LL d = min(solve(l, mid), solve(mid + 1, r));
        int sz = 0;
        for (int i = l; i <= r; ++i)
        {
            if (sqr(llabs(p[i].x - p[mid].x)) <= d)
                temp[sz++] = p[i];
        }
        sort(temp, temp + sz, cmpy);
        for (int i = 0; i < sz; ++i)
        {
            for (int j = i + 1; j < sz; ++j)
            {
                if (sqr(temp[j].y - temp[i].y) >= d)
                    break;
                d = min(d, dis(temp[j], temp[i]));
            }
        }
        return d;
    }
}
int arr[N], pre[N];
int Scan()
{
    int res = 0, ch, flag = 0;
    if ((ch = getchar()) == '-')            //判断正负
        flag = 1;
    else if (ch >= '0' && ch <= '9')          //得到完整的数
        res = ch - '0';
    while ((ch = getchar()) >= '0' && ch <= '9' )
        res = res * 10 + ch - '0';
    return flag ? -res : res;
}
int main(void)
{
    register int n, i;
    scanf("%d", &n);
    for (i = 1; i <= n; ++i)
    {
        arr[i] = Scan();
        pre[i] = pre[i - 1] + arr[i];
        p[i].x = i;
        p[i].y = pre[i];
    }
    sort(p + 1, p + n + 1, cmpx);
    printf("%lld\n", solve(1, n));
    return 0;
}