哪个网站做黄金交易最好,昆山网站建设怎么样,西安seo推广公司,腾讯广告代理题目链接
题目 题目大意 T T T 组测试数据 每组 n n n 个货物#xff0c;第 i i i 个货物 的重量是 a i a_i ai 用k辆货车按顺序装这些货物#xff0c;条件是每辆车上的货物个数都一样#xff0c;也即是说 n n n 必须能被 k k k 整除#xff0c; 求任意两辆车货物总…题目链接
题目 题目大意 T T T 组测试数据 每组 n n n 个货物第 i i i 个货物 的重量是 a i a_i ai 用k辆货车按顺序装这些货物条件是每辆车上的货物个数都一样也即是说 n n n 必须能被 k k k 整除 求任意两辆车货物总重量的最大的差值。
思路
这题直接是暴力枚举细节见代码
代码
#includebits/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;}
