题目链接
这篇文章中， “基本思路”部分会详细介绍我最真实的推理过程，可能会有些啰嗦，还会包括一些显而易见随手推一推就能推出来的结论的证明，这些结论我已经用粗体字标注出来了。
基本思路
观察样例，显然：
当n可以被k整除时，整个环可以拆分成k个互不相关的环。
样例中，k=2时，可以将最优方案看成3,1,2和6,4,5两个集合中任意两个距离为1的数的乘积的和。
当一个环中只有三个数，并且k=1（也就是要求相邻两个数乘积的和）时，三个数的位置并不会影响最终结果，因为每个数都会和另外两个数分别乘一次。所以把三个最小的数 和三个最大的数 组合在一起，就是最优解。
这个结论比较容易想到，以下是证明过程：
n=6，k=3 时的证明
尝试把两个集合中的任意一个数互换位置。比如互换1和6，那么两个集合就会变成3,6,2和1,4,5，比较第一个集合算出的结果在这次交换后上升的值 和 第二个集合（算出的结果）在交换后下降的值，它们分别为(6−1)∗(3+2)和(6−1)∗(4+5)，不论交换哪两个数，两个式子第一个乘数都相等。而第二个乘数中，第二个集合总比第一个集合大。综上所述，第一个集合上升的值比第二个集合下降的值要小，它们的和会下降。
而我们很容易把这个证明推广到正整数范围。
那么当n不能被k整除时呢？
先说结论：当k不能整除n时，只要n不变，最大值就确定
理论
还是举个例子：
比如n=7, k=3时，这个环为1,2,3,4,5,6,7时，算出的和为：
$14+47+73+36+62+25+5*1$
显然（其实我也不知道是为什么），没有重复和遗漏，并且按照这个顺序，我们也可以把它看成7个数的环中，相邻的两个数乘积的和，只不过是这个“相邻”指的是距离为k的两个数。
和传统意义上的“相邻”（即k=1）一样，这个环上的每个数有且仅有两个数和它相乘。对于这道题，唯一的不同点在于，对于同样的一个环，k会影响其最后算出的和。但是对于本题中求的最大值，我们可以在算出k=1（因为这比较方便计算）后再去调整“相邻”
例子：如何变换
比如n=7，k=1时，这个环是这样的：
1,2,3,4,5,6,7
算出的和为：
1∗2+2∗3+3∗4+4∗5+5∗6+6∗7+7∗1
当k=3时，如何变换这个环，使算出来的值等于k=1是的值呢？（以下步骤使用x表示未知数）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| // 首先，将1（第1个数，后同理）填入任何一个位置（因为是一个环，首尾相接，绝对未知并不会影响最终结果。为方便演示，填到[0]的位置）
{1, x, x, x, x, x, x}
// 找到与1相邻的位置，填2
{1, x, x, 2, x, x, x} 或 {1, x, x, x, 2, x, x} //两种分别对应往前数和往后数，后省略，以第一种为例
// 找到另一个与2相邻的位置（即两个位置中未知的那个），填3
{1, x, x, 2, x, x, 3}
// 以此类推，找到另一个与n相邻的未知，填(n+1)
{1, x, 4, 2, x, x, 3}
{1, x, 4, 2, x, 5, 3}
{1, 6, 4, 2, x, 5, 3}
{1, 6, 4, 2, 7, 5, 3}
|
相信在这个过程中，可以生动体会到上面的理论
于是，将这个环代入计算，过程和结果与上面的完全一致。
找出最大值
上面说了那么多，总结起来一句话：当n与环a一定，且k不整除n时，最大值不随k变化而变化（k这时可以当作1）
而当k整除n时，又可以拆成k个小环，而每个子环都可以看成是n=(n/k)，$ k=1$的环。
这样，我们就把两种情况统一成一种了。
唯一例外的是，当k为一个完全平方数，且sqrt(k)整除n时，可以看作是k=sqrt(k)
现在要实现的就是，当k=1时，怎样排列可以使这个值最大。
实例
可以参考样例中k=1, n=6时的排列：
可以发现和6相邻的为4和5，和5相邻的另一个数是3，和4相邻的另一个数是2。
这样排列把最大的数放在了一起，然后从大到小排列，尽可能把大的数放在一起。我会用n=7, k=1来演示这个过程
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| {x, x, x, x, x, x, x} //初始状态
// 在任意位置放7,并且时6,5与7相邻
{x, x, 5, 7, 6, x, x}
// 在6旁边放剩余的最大的数
{x, x, 5, 7, 6, 4, x}
// 在5旁边放剩余最大的数
{x, 3, 5, 7, 6, 4, x}
// 重复这一过程，每次将 相邻位置有空位的最大数 的 另一个位置填上剩余最大数
{x, 3, 5, 7, 6, 4, 2}
{1, 3, 5, 7, 6, 4, 2}
|
这种方法貌似时有一种贪心思想在内，要想证明这种方法有效， 可以用类似上面的证明方法，这里不再赘述。
实际应用与代码
在多举几个例子后，会发现，在代码中，并不需要使用一个数组来真正存储它，只需要实现这样一个函数：
1
2
3
4
5
6
7
8
9
10
11
| unsigned long long ch(unsigned long long l){
unsigned long long aa=0;
aa+=a[z]*a[z+1];
for(int i=0; i<l-2; i++){
aa+=a[z]*a[z+2];
z++;
}
aa+=a[z]*a[z+1];
z+=2;
return aa;
}
|
基本原理就是上面的一大堆，自己稍微推一下就会得出这个算法。
代码
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
| #include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
const int len=2*1e5+5;
unsigned long long n, m, k, z, re;
unsigned long long ans, a[len];
bool cmp(int a, int b) { return a>b; }
unsigned long long ch(unsigned long long l){
unsigned long long aa=0;
aa+=a[z]*a[z+1];
for(int i=0; i<l-2; i++){
aa+=a[z]*a[z+2];
z++;
}
aa+=a[z]*a[z+1];
z+=2;
return aa;
}
int main(){
freopen("ring.in", "r", stdin);
freopen("ring.out", "w", stdout);
scanf("%lld %lld", &n, &m);
for(int i=0; i<n; i++){
scanf("%lld", &a[i]);
}
sort(a, a+n, cmp);
for(int i=0; i<m; i++){
scanf("%lld", &k);
ans=0;
if((k!=0) && ((n/k)*k!=n) && (int(sqrt(k))*int(sqrt(k))==k)) k=int(sqrt(k));
if(k==0){
for(int j=0; j<n; j++) ans+=a[j]*a[j];
}
else if((n/k)*k==n){
z=0;
for(int j=0; j<k; j++){
ans+=ch(n/k);
}
}
else{
if(re>0) ans=re;
else{
z=0;
ans=ch(n);
re=ans;
}
}
printf("%lld\n", ans);
}
return 0;
}
|