CF429D Tricky Function 题解 分治/平面最近点对

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

题目大意：

给定一个长度为 \(n\) 的数列 \(a_1, a_2, \ldots, a_n\)。

用 \(s\) 表示 \(a\) 的前缀和数组，即 \(s_i = \sum\limits_{j = 1}^i a_j\)

定义 \(f(i, j) = (i - j)^2 + (s_i - s_j)^2\)

求所有 \(i \neq j\) 的 \(f(i, j)\) 的最小值。

解题思路：

平面最近点对。

将 \(i\) 作为横坐标，\(s_i\) 作为纵坐标，\((i - j)^2 + (s_i - s_j)^2\) 作为两点之间距离。求平面最近点对。

示例程序（在平面最近点对代码上稍作了一点修改）：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;

struct Node {
    long long x, y;
} a[maxn], b[maxn];

bool cmp_x(Node a, Node b) {
    return a.x < b.x;
}

bool cmp_y(Node a, Node b) {
    return a.y < b.y;
}

long long dis(Node a, Node b) {
    return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}

int n;
long long A[maxn];

long long solve(int l, int r) {
    if (l >= r) return 2e9;
    int mid = (l + r) / 2;
    long long d = min(solve(l, mid), solve(mid+1, r));
    int p = 0;
    for (int i = l; i <= r; i++) if ((a[i].x - a[mid].x) * (a[i].x - a[mid].x) < d) b[p++] = a[i];
    sort(b, b+p, cmp_y);
    for (int i = 0; i < p; i++)
        for (int j = i+1; j < p && (b[j].y - b[i].y) * (b[j].y - b[i].y) < d; j++)
            d = min(d, dis(b[i], b[j]));
    return d;
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%lld", A+i);
        A[i] += A[i-1];
        a[i].x = i;
        a[i].y = A[i];
    }
    sort(a+1, a+n+1, cmp_x);
    printf("%lld\n", solve(1, n));
    return 0;
}