[CF429D] Tricky Function

[CF429D] Tricky Function - 平面最近点对

Description

定义函数 (f(i,j)=(i-j)^2+(displaystylesum_{k=min(i,j)+1}^{max(i,j)} a_k )^2)
求 (displaystylemin_{i e j}f(i,j))。(abs(a_i) le 10^4)

Solution

转化为 2D 平面最近点对问题

考虑到 (a_i) 的范围，横坐标的差也不会太大，所以暴力检查 (i,j), (abs(i,j) le M) 即可，其中 (M) 为设定的横座标上界

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1000005;
const int M = 2005;
int n, a[N], ans = 1e18;
signed main()
{
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i], a[i] += a[i - 1];
    for (int i = 1; i <= n; i++)
        for (int j = max(1ll, i - M); j < i; j++)
            ans = min(ans, (j - i) * (j - i) + (a[j] - a[i]) * (a[j] - a[i]));
    cout << ans << endl;
}