Preface
乱猜结论 并且懒得 implement 害人不浅。
Problem
给 \(a_1 \sim a_n\) 重排列，最大化 \(\sum\limits_{i=1}^n \lvert pa_i - qa_{i+1} \rvert\)，其中 \(a_{n+1} = a_1\)。
Solution
refer to 官方解法。
贪心的原则基于一个前提：\(\lvert a \rvert = \max\{a, -a\}\)。
这告诉我们，以后遇到带绝对值再最大化的题目，先考虑拆掉绝对值。
感觉讲的有点少，那么来聊点别的，比如这题如何构造方案（构造性证明上面是对的）。
我们假设 \(p \lt q\)，最后一定是留下这些元素：
- \(a_i : +p, +q\)，记为 \(\text A\) 类元素
- \(a_i : -p, +q\)，记为 \(\text B\) 类元素
- \(a_i : -p, -q\)，记为 \(\text C\) 类元素
有人看不懂，说一句，比如 \(\text A\) 类元素的记号就是我们要留下 \(+pa_i\) 和 \(+qa_i\) 这种。
因为 \(+p\) 和 \(+q\) 的总和是 \(n\) 个，\(+q\) 和 \(-q\) 的总和也是 \(n\) 个，所以 \(\text A\) 的个数 \(= \text C\) 的个数。
那么构造就比较显然了：先把 \(\text B\) 连起来，然后一个 \(\text C\) 一个 \(\text A\) 的选。
这个是对的，证明就是你写一下确实 \(+p\) 对应 \(-q\)，\(-p\) 对应 \(+q\)，只要你是严格按照这个顺序写的都不会有问题，毕竟前 \(n\) 大肯定大于后 \(n\) 大。注意 \(p \gt q\) 的时候 \(\text A, \text C\) 顺序要反一下。
然后这个也就比较证明了为什么正着和反着交替选总有一个是对的。
Code
#include <bits/stdc++.h>
#define MAXN 1000001
int a[MAXN];
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
int N; long long p, q; std::cin >> N >> p >> q;
for (int i = 1; i <= N; ++i) std::cin >> a[i];
std::sort(a + 1, a + N + 1);
for (int i = N, j = N; ; ) {
(p * a[i] >= q * a[j] ? i : j) -= 1;
if (i + j == N) {
// assume i < j :
// [1, i] : C
// [i + 1, j] : B
// [j + 1, N] : A
// i > j, swap(C, A)
std::vector<int> s;
for (int k = std::min(i, j) + 1; k <= std::max(i, j); ++k) s.push_back(a[k]);
int c = (i < j ? 1 : i + 1), d = (i < j ? j + 1 : 1);
for (; std::max(c, d) <= N; ++c, ++d)
s.push_back(a[c]), s.push_back(a[d]);
long long ans = std::abs(p * s[N - 1] - q * s[0]);
for (int i = 0; i + 1 < N; ++i)
ans += std::abs(p * s[i] - q * s[i + 1]);
std::cout << ans << '\n';
for (int i = 0; i < N; ++i)
std::cout << s[i] << " \n"[i + 1 == N];
return 0;
}
}
return 0;
}