Codeforces ラウンド #245 (ディビジョン 1)??トリッキーな関数_html/css_WEB-ITnose

質問リンク

質問の意味:
n 数値 a[i], f(i, j) = (i - j) ^ 2 + sigma(a[k]) ^ 2, i n (2?≤?n?≤?100000).(?-?104?≤?a[i]?≤?104)

分析:
鍵は質問変換の意味。単純な考慮に基づいて、各区間の情報を知る必要があり、質問の f 関数を簡素化する必要があります。区間を考慮することは現実的ではないので、区間が 2 つの短い点に分割できるかどうかを計算してみます。ここでは一般的な変換が使用されます。つまり、間隔の合計がプレフィックスの合計の差に変換されます。変換後、 f(i, j) = (i - j) ^ 2 + (presum[j] - presum[i]) ^ 2 が得られます。幾何学をやったことがある人なら誰でも、それが図形上の最も近い点のペアであることがわかります。平面

要約:
問題の単位として間隔を使用すると、複雑さを軽減するのが難しいため、問題の考慮単位は多くの場合ポイントになります。ポイントに変換できれば、複雑さは軽減されます。
区間の合計はプレフィックスの合計に変換する必要があることがよくあります。この場合、区間内の 2 つの点について、計算する必要がある値は現在の点、つまり前のタスク (区間を に変換する) にのみ関連します。ポイント）が完了しました

const double EPS = 1e-10;const int MAXN = 100100;inline int dcmp(double x){	if(fabs(x) < EPS) return 0;	else return x < 0 ? -1 : 1;}struct Point{	LL x, y;};//最近点对Point point[MAXN];LL tmpt[MAXN], Y[MAXN];inline bool cmpxy(Point a, Point b){	if(a.x != b.x)		return a.x < b.x;	return a.y < b.y;}inline bool cmpy(int a, int b){	return point[a].y < point[b].y;}inline LL dist(int x, int y){	Point& a = point[x], &b = point[y];	return sqr(a.x - b.x) + sqr(a.y - b.y);}LL Closest_Pair(int left, int right){	LL d = 1e18;	if(left == right)		return d;	if(left + 1 == right)		return dist(left, right);	int mid = (left + right) >> 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) <= d)			tmpt[k++] = i;	}	sort(tmpt, tmpt + k, cmpy);	//线性扫描	REP(i, k)		for(int j = i + 1; j < k && sqr(point[tmpt[j]].y-point[tmpt[i]].y) < d; j++)		{			LL d3 = dist(tmpt[i],tmpt[j]);			if(d > 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 << ans << endl;	}	return 0;}