题目链接

题目

题目大意

$T$ 组测试数据
每组 $n$ 个货物，第 $i$ 个货物 的重量是 $a_i$
用k辆货车按顺序装这些货物，条件是每辆车上的货物个数都一样，也即是说 $n$ 必须能被 $k$ 整除，
求任意两辆车货物总重量的最大的差值。

思路

这题直接是暴力枚举，细节见代码

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 10;
int a[N], sum[N], back[N];
bool isPrime(int n) {if (n == 1) return false;if (n == 2 || n == 3 || n == 5 || n == 7) return true;//只需判断一个数能否被小于sqrt(n)的奇数整除for (int i = 2; i <= sqrt(n); i ++) {if(n % i == 0) {return false;}}return true;
}
signed main()
{int T; cin >> T;while (T -- ){int n;scanf("%lld", &n);for (int i = 0; i <= n; i ++ ) sum[i] = 0;for (int i = 1; i <= n; i ++ ){scanf("%lld", &a[i]);back[i] = a[i];sum[i] = sum[i - 1] + a[i];}//		只有一个数时输出0 if (n == 1){cout << 0 << endl;continue;}
//		for (int i = 1; i <= n; i ++ )
//		{
//			cout << sum[i] << " ";
//		}
//		cout << endl;sort(back + 1, back + 1 + n);//		如果每个数都一样，直接输出0 int ma = back[n] - back[1];if (ma == 0){printf("%lld\n", ma);continue;}//		开始枚举每一个 for (int  i = 2; i <= n / 2; i ++ ){if (n % i == 0){int m1 = 0, m2 = 99999999999999999;int l = 0, r = i; //双指针进行枚举//				一共装n/i辆货车 for (int j = 1; j <= n / i; j ++ ){
//					算出这辆货车的货物重量 int x = sum[r] - sum[l];//					求最大的重量和最小的重量 m1 = max(x, m1);m2 = min(x, m2); //					找下一辆车 l += i;r += i;}
//				找最大的差值 ma = max(ma, abs(m1 - m2));//				算一遍i辆货车时的情况 m1 = 0, m2 = 99999999999999999;l = 0, r = n / i;for (int j = 1; j <= i; j ++ ){int x = sum[r] - sum[l];m1 = max(x, m1);m2 = min(x, m2);l += (n / i);r += (n / i);}ma = max(ma, abs(m1 - m2));}}printf("%lld\n", ma);}return 0;}