自动搬运

查看原文

来自洛谷，原作者为

	Dengxy **

搬运于2025-08-24 22:30:53，当前版本为作者最后更新于2021-10-29 16:20:15，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

此题数据范围与题面不符，原题传送门。

Description

将一个环分为 $t$ 部分，第 $i$ 个部分长度为 $s_i$，所有部分的平均长度为 $s_{avg}$ ，求 $\min\{t^2\sum (s_i - s_{avg})^2\}$.

Solution

设 $t$ 个部分总长度为 $sum_n$，有 $s_{avg} = \frac{sum_n}{t}$

那么答案即为

$$t^2\sum (s_i - s_{avg})^2 = t^2\sum s_i^2 - t \times sum_n^2. $$

k = 2

此时就是将环分成两部分，使得前一部分刚好小于 $s_{avg}$即可。

k = 3

和 $k = 2$ 的情况一样，换成三部分即可。但是由于不一定分出的结果是最好的，所以要处理边界，尝试将分割点左右移动，找最小值。

k > 3

由于 $t,sum_n$ 为常数，所以答案只与每部分长度的平方和有关。

于是问题转化为：将一个数列分为 $t$ 部分，最小化每部分的平方和。

令 $dp_{i,j}$ 表示前 $i$ 个数，分为 $j$ 部分，用 $sum_i$ 表示前 $i$ 部分的前缀和，得出状态转移方程：

$$dp_{i,j} = \min\limits_{0<k<i}\{ dp_{k,j-1} + (sum_i - sum_k)^2\} $$

$dp_{i,j}$ 只与 $dp_{k,j-1}$ 有关，可以用滚动数组优化空间。将二次项拆开后，发现出现 $sum_i \times sum_j$ ，考虑用斜率优化。

设 $i_1 < i_2$ 且 $dp_{i_1,j} < dp_{i_2,j}$，所以：

$$dp_{i_1,j-1} + (sum_i-sum_{i_1})^2 < dp_{i_2,j-1} + (sum_i-sum_{i_2})^2 $$

即：

$$2 \times sum_i < \frac{dp_{i_2,j-1}+sum_{j_2}-(dp_{i_1,j-1}+sum_{j_1})}{sum_{j_2}-sum_{j_2}} $$

令 $Y(x) = dp_{x,j-1}+sum_x,X(x)=sum_x,$则：

$$\frac{Y(i_2)-Y(i_1)}{X(i_2)-X(i_1)} > 2 \times sum_i $$

最后直接斜率优化即可，时间复杂度 $O(n^2k)$。

Code

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N = 3e5 + 10;
int n,t,ans = 0x3f3f3f3f3f3f3f3f;;
int l[N],a[N],s[N];
int x[N],y[N],Fun[N],head,tail;
int f[N][2];

double slope(int j1,int j2)
{
	return 1.0 * (y[j2] - y[j1]) / (x[j2] - x[j1]);
}

void solve2()
{
	for(int i = 1;i <= n;++ i)
		s[i] = s[i-1] + l[i];
	int tmp = s[n] >> 1,pos = 0;
	int sum = 0;
	for(int i = 1;i <= n;++ i)
	{
		while(sum < tmp)
		{
			pos = pos + 1 > n ? 1 : pos + 1;
			sum += l[pos];
		}
		ans = min(ans,sum * sum + (s[n] - sum) * (s[n] - sum));
		sum -= l[i];
	}
	printf("%lld\n",t * t * ans - t * s[n] * s[n]);
}

void solve3()
{
	for(int i = 1;i <= n;++ i)
		s[i] = s[i-1] + l[i];
	int tmp = s[n] / 3;
	int pos1 = 1,pos2 = 1,sum1 = 0,sum2 = 0;
	for(int i = 1;i <= n;++ i)
	{
		while(sum1 < tmp)
		{
			if(pos1 < pos2) sum2 -= l[(pos1 - 1) % n + 1];
			//由于涉及第二段减去第一段选择的长度，用取模代替滚动 
			sum1 += l[(pos1 - 1) % n + 1];
			++ pos1;
		}
		pos2 = max(pos2,pos1);
//		printf("sum2 after pos1:%lld ,pos2:%lld\n",sum2,pos2);
		while(sum2 + l[(pos2 - 1) % n + 1] <= s[n] - sum1 - sum2 - l[(pos2 - 1) % n + 1])//使两边尽量均衡 
		{
			sum2 += l[(pos2 - 1) % n + 1];
			++ pos2;
		}
		
		int sum3 = s[n] - sum1 - sum2,sum4;
		ans = min(ans,sum1 * sum1 + sum2 * sum2 + sum3 * sum3);
		
		sum3 = sum2 + l[(pos2 - 1) % n + 1],sum4 = s[n] - sum1 - sum3;
		ans = min(ans,sum1 * sum1 + sum3 * sum3 + sum4 * sum4);
//		printf("%lld pos:%lld %lld len:%lld %lld %lld or %lld %lld %lld\n",i,pos1,pos2,sum1,sum2,s[n] - sum1 - sum2,sum1,sum3,sum4);
		sum1 -= l[i];
	}
	printf("%lld\n",t * t * ans - t * s[n] * s[n]);
}

signed main()
{
	scanf("%lld%lld",&n,&t);
	for(int i = 1;i <= n;++ i)
		scanf("%lld",&l[i]);
		
	if(t == 2)
	{
		solve2();
		return 0;
	}
	if(t == 3)
	{
		solve3();
		return 0;
	}
	
	for(int pos = 1;pos <= n;++ pos)
	{
		int cnt = 0,p = 0;
		for(int i = pos;i <= n;++ i)
			a[++cnt] = l[i];
		for(int i = 1;i < pos;++ i)
			a[++cnt] = l[i];
		s[0] = 0;
		for(int i = 1;i <= n;++ i)
		{
			s[i] = s[i-1] + a[i];
			f[i][p^1] = s[i] * s[i];
		}
		
		for(int j = 2;j <= t;++ j)
		{
			head = 1,tail = 1;
			for(int i = 1;i <= n;++ i)
			{
				while(head < tail && slope(Fun[head],Fun[head+1]) <= 2 * s[i])
					++ head;
				
				int k = Fun[head];
				f[i][p] = f[k][p^1] + (s[i] - s[k]) * (s[i] - s[k]);
				x[i] = s[i];
				y[i] = f[i][p^1] + s[i] * s[i];
				
				while(head < tail && slope(Fun[tail-1],Fun[tail]) >= slope(Fun[tail],i))
					-- tail;
				//维护一个下凸包 
				
				Fun[++tail] = i;
			}
			p ^= 1;
		}
		ans = min(ans,f[n][p^1]);
	}
	printf("%lld\n",t * t * ans - t * s[n] * s[n]);
	return 0;
}