正经题解｜捞薯条

题目大意

$n$箱薯条，选择$\frac{n}{k}$辆卡车来运输，每辆卡车运输连续的$k$箱薯条，求在所有可行的情况下，卡车最大载重和最小载重的差值。

题目思路

根据题意，每辆卡车必须装满$k$箱，且卡车数是$\frac{n}{k}$，所以卡车数辆必须是$n$的约数。所以枚举每一个$i$，代表车辆装载连续的$i$箱，然后求出当下情况载重的最大差值。
考虑到要多次计算连续的一段的和，所以可以使用前缀和进行优化，降低计算区间和的时间复杂度。

时间复杂度分析

该算法的时间复杂度主要集中在枚举每个$n$的约数，然后统计序列中每段连续的$n$个数，然后求极差。解决问题函数时间复杂度在有前缀和优化后几乎等于 $O(n)$ 。

代码演示

#include<bits/stdc++.h>
using namespace std;
long long arr[1000005];
void solve()
{
	int n;
	cin >> n;
	for(int i = 1 ; i <= n ; i ++ )cin >> arr[i];
	for(int i = 1 ; i <= n ; i ++)
	{
		arr[i] += arr[i-1];
	}
	long long answer = 0 ;
	for(int i = 1 ; i <= n ; i ++ )
	{
		if(n % i || n / i < 2)continue;
		long long mi = 1e18 + 7 ;
		long long mx = -1;
		for(int k = i ; k <= n ; k += i )
		{
			
			mx = max(mx,arr[k] - arr[k - i]);
			mi = min(mi,arr[k] - arr[k - i]);
		}
		answer = max(mx - mi , answer);
	}	
	cout << answer << endl;
}

int main()
{
	int t;
	cin >> t;
	while(t--)
	{
		solve();
	}
	return 0;
}