题意：给定一个数组你个数的数组a，定义sum(i, j)表示sigma(a[i],...a[j]),以及另外一个函数f(i, j) = (i - j)^2 + sum(i+1, j)^2
求最小的f(i, j)(i < j)
思路：变形一下f(i, j) = (i - j)^2 + (sum[j] - sum[i])^2
那么把i看成x，sum[i]看成y，那就等价于求二维平面的最近点对吗。
二维平面求最近点对有一个经典nlognlogn的分治算法。。
code：
1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 typedef pair<int, int> pii; 5 #define x first 6 #define y second 7 const int Inf = 0x3fffffff; 8 pair<int, int> p[101010], tmp[101010]; 9 int n; 10 ll dis(int x, int y, int x1, int y1){ 11 ll dx = x - x1, dy = y - y1; 12 return dx * dx + dy * dy; 13 } 14 15 bool cmp(const pii& a, const pii& b){ 16 return a.y < b.y; 17 } 18 19 ll X, Y, k; 20 ll solve(const int l,const int r){ 21 if (l == r) return Inf; 22 int m = (l + r) >> 1; 23 ll d = solve(l, m), d1 = solve(m+1, r); 24 d = min(d, d1); 25 k = 0; 26 X = p[m].x; 27 for (int i = l; i <= r; ++i) 28 if ((X-p[i].x) * (X-p[i].x) <= d) tmp[k++] = p[i]; 29 sort(tmp, tmp + k, cmp); 30 for (int i = 0; i < k; ++i){ 31 Y = tmp[i].y; 32 for (int j = i+1; j < k; ++j){ 33 if ((Y - tmp[j].y) * (Y - tmp[j].y) > d) break; 34 d = min(d, dis(tmp[i].x, tmp[i].y, tmp[j].x, tmp[j].y)); 35 } 36 } 37 return d; 38 } 39 40 void solve(){ 41 p[0] = make_pair(0, 0); 42 int u; 43 for (int i = 1; i <= n; ++i) 44 scanf("%d", &u), p[i].x = i, p[i].y = p[i-1].y + u; 45 ll ans = solve(1, n); 46 cout << ans << endl; 47 } 48 49 int main(){ 50 // freopen("a.in", "r", stdin); 51 while (scanf("%d", &n) != EOF){ 52 solve(); 53 } 54 }