题目链接
n个数a[i]，f(i, j) = (i - j) ^ 2 + sigma(a[k]) ^ 2, i n (2?≤?n?≤?100000).(?-?104?≤?a[i]?≤?104)
关键在于题意的转换。简单的考虑，需要知道每个区间的信息，复杂度难以降下来，应该将题目的f函数进行化简。既然考虑区间是不可行的，那么就尝试是否能将区间分成两个短点的计算。这里用到了一个常用的转换：区间和转化为前缀和的差。转换后就得到f(i, j) = (i - j) ^ 2 + (presum[j] - presum[i]) ^ 2，做过几何的都能看出来，就是平面最近点对
如果以区间为问题的单位，那么复杂度难以下降，所以问题的考虑单位往往是点，如果能转化为点，复杂度将可以下降
区间和往往需要转化为前缀和：这样的话，对于区间的两个点，需要求得值就只和当前点有关，也就是完成了上一个（区间转化为点）的任务
const double EPS = 1e-10;const int MAXN = 100100;inline int dcmp(double x){ if(fabs(x) > 1; double d1 = Closest_Pair(left, mid); double d2 = Closest_Pair(mid + 1, right); d = min(d1, d2); int k = 0; //分离出宽度为d的区间 FE(i, left, right) { if(sqr(point[mid].x - point[i].x) d3) d = d3; } return d;}LL ipt[MAXN];int main(){ //freopen("input.txt", "r", stdin); int n; while (~RI(n) && n) { FE(i, 1, n) { cin >> ipt[i]; ipt[i] = ipt[i - 1] + ipt[i]; } FE(i, 1, n) { point[i - 1].x = i; point[i - 1].y = ipt[i]; } sort(point, point + n, cmpxy); LL ans = Closest_Pair(0, n - 1); cout