CF1899B 250 Thousand Tons of TNT

题目链接

题目

题目大意

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

思路

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

代码

#include
#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;
 } 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101