整理的算法模板合集： ACM模板
CF429D Tricky Function
题意实际上就是给定长度为 n n n 的一串序列 a 1 , a 2 , . . . , a n a_1, a_2,...,a_n a1,a2,...,an，找到两个正整数 i , j ∈ [ 1 , n ] i,j\in[1,n] i,j∈[1,n]，求 ( i − j ) 2 + ( ∑ k = i + 1 j a k ) 2 (i-j)^2+(\sum_{k=i+1}^{j}a_k)^2 (i−j)2+(∑k=i+1jak)2 的最小值
分析 将原式中的 ∑ k = i + 1 j a k \sum_{k=i+1}^{j}a_k ∑k=i+1jak用前缀和 S j − S i S_j-S_i Sj−Si替代，则原式变换为 ( i − j ) 2 + ( S j − S i ) 2 (i-j)^2+(S_j-S_i)^2 (i−j)2+(Sj−Si)2
不难看出变换后的式子为两点之间欧几里德距离的平方，于是原题转化为求平面上的最近点对距离的平方。
关于最近点对距离的求解可使用二分法
注意本题的数据会卡普通的 O ( n l o g n ) O(nlogn) O(nlogn)的分治求平面最近点对算法，我们需要加一些玄学优化，比如在筛y轴的时候一旦大于d就直接break，因为是排过序的，当前的y都大了，说明接下来的所有点都不能用了。
#include<cstdio> #include<algorithm> #include<cmath> #define R register using namespace std; const int N = 200007; typedef long long ll; struct Point { ll x, y; bool operator < (const Point& t)const { return y < t.y; } }; Point v[N], tmp[N]; int n; ll get_dist(Point A, Point B) { return (ll)(A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y); } ll solve(const int l, const int r){//求平面最近点对的分治算法 if(l == r)return 0x3f3f3f3f3f; if(l + 1 == r)return get_dist(v[l], v[r]);//分治到了一个点对，直接返回答案 int mid = (l + r) >> 1; ll d1 = solve(l, mid), d2 = solve(mid + 1, r); ll d = min(d1, d2); int tot = 0; //先筛选x for(int i = l; i <= r; ++ i){ if((v[mid].x - v[i].x) * (v[mid].x - v[i].x) <= d)tmp[ ++ tot] = v[i]; } sort(tmp + 1, tmp + tot + 1);//按y排序 //再筛选y for(int i = 1; i <= tot; ++ i){ for(int j = i + 1; j <= tot; ++ j){ if((tmp[i].y - tmp[j].y) * (tmp[i].y - tmp[j].y) > d)break;//剪枝优化，不加过不了本题 d = min(d, get_dist(tmp[i], tmp[j])); } } return d; } int main() { scanf("%d", &n); for(int i = 1; i <= n; ++ i){ int x; scanf("%d", &x); v[i].y = v[i - 1].y + x;//y就是前缀和，我们通过公式推出来的 v[i].x = i; } ll minv = solve(1, n); printf("%lld\n", minv); return 0; }