数组重排求最大相邻和：我的解法部分测试用例错误，求逻辑漏洞排查

先明确F(A)的数学本质 #

首先推导F(A)的核心表达式：
对于数组A = [a₀, a₁, ..., a(n-1)]，相邻元素对的和之和展开后可简化为：

F(A) = 2 * sum(所有元素) - a₀ - a(n-1)

这意味着：要最大化F(A)，只需要最小化首尾元素的和a₀ + a(n-1)——也就是把数组中最小的两个元素放在首尾位置，剩下的元素无论怎么排列，总和都是最大值。

你的代码的致命问题 #

1. 元素重复使用：构造sol数组时，你两次从原数组中取元素（第一次升序取偶索引，第二次降序取偶索引），会导致sol中出现重复元素（比如n为奇数时，部分元素被多次选中），完全违反了“重排数组元素需每个元素恰好使用一次”的要求。
2. 排列逻辑偏离最优解：你通过试错得到的排列方式没有抓住问题的数学本质，即使元素不重复，也无法保证首尾是最小的两个元素，从而无法得到最大的F(A)。

正确解法思路 #

根据推导的公式，最优解的实现可以分为两种方式：

方式1：构造最优排列并计算 #

排序数组后，将最小的元素放在开头，第二小的放在末尾，中间元素按任意顺序排列（比如降序，不影响结果）：

#include <iostream>
#include <algorithm> 
#include <vector>    

using namespace std;

int calculateFunction(vector<int>& arr) {
    int sum = 0;
    for (int i = 0; i < arr.size() - 1; i++) {
        sum += arr[i] + arr[i + 1];
    }
    return sum;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> arr(n);
        for (int j = 0; j < n; j++) {
            cin >> arr[j];
        }
        sort(arr.begin(), arr.end());
        
        vector<int> sol;
        sol.push_back(arr[0]);
        // 中间放从大到小的元素，末尾自然是第二小的元素
        for (int j = n-1; j >= 1; j--) {
            sol.push_back(arr[j]);
        }
        
        cout << calculateFunction(sol) << endl;
    }
    return 0;
}

方式2：直接通过公式计算（更高效） #

不需要构造排列，直接利用公式计算最大值，避免额外的数组操作：

#include <iostream>
#include <algorithm> 
#include <vector>    

using namespace std;

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> arr(n);
        long long sum = 0; // 用long long防止数值溢出
        for (int j = 0; j < n; j++) {
            cin >> arr[j];
            sum += arr[j];
        }
        sort(arr.begin(), arr.end());
        long long max_f = 2 * sum - arr[0] - arr[1];
        cout << max_f << endl;
    }
    return 0;
}

内容的提问来源于stack exchange，提问作者Akshat Parashar