题解：CF1899B 250 Thousand Tons of TNT

原题链接

• 洛谷 CF1899B 250 Thousand Tons of TNT

解题思路

显然 $n$ 必须是 $k$ 的倍数才能使每辆车的箱子数量相同，所以 $n$ 的因子就是所有可能的 $k$。

枚举 $n$ 的所有因子，对于每个因子 $k$，用前缀和计算 $\frac{n}{k}$ 辆车重量的极差，最后取最大值即为答案。

时间复杂度低于调和级数：$O(\sum_{d|n}\frac{n}{d})<O(\sum_{i=1}^{n}\frac{n}{i})=O(n\log{n})$。

参考代码

#include <bits/stdc++.h>
using namespace std;
 
using ll=long long;
const ll inf=0x3f3f3f3f3f3f3f3f;
const int N=150005;
ll a[N];
ll f(int n,int k)
{
	ll mx=-inf,mn=inf;
	for(int i=0;i<n/k;i++)
	{
		ll val=a[k*(i+1)]-a[k*i];
		mx=max(mx,val);
		mn=min(mn,val);
	}
	return mx-mn;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int T;
	cin>>T;
	while(T--)
	{
		int n;
		cin>>n;
		for(int i=1;i<=n;i++)
		{
			cin>>a[i];
			a[i]+=a[i-1];
		}
		ll ans=-inf;
		for(int i=1;i<=n;i++)
		{
			if(n%i==0)
			{
				ans=max(ans,f(n,i));
			}
		}
		cout<<ans<<'\n';
	}
	return 0;
}