最大化数组中相邻总和的总和

Question

对于下面提到的问题，我得到了一些测试用例的错误答案，我已经进一步解释了我的方法。请帮我找出我的逻辑缺陷。

问题陈述：给你一个大小为（N≥2）的数组A。 F(A) = (A(i) + A(i+1)) 之和；例如：对于数组 A[1,2,3] ， f(a) = (1+2)+(2+3) 通过以任意顺序重新排列 A 的元素，找到 f(A) 的最大值。 问题链接：

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

using namespace std;

bool compare(int a, int b) {
    return a > b;
}

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(n);
        int x = 0;
        for (int j = 0; j < n; j += 2) {
            sol[x++] = arr[j];
        }
        sort(arr.begin(), arr.end(), compare);
        for (int j = 0; j < n; j += 2) {
            sol[x++] = arr[j];
        }
        int sum = calculateFunction(sol);
        cout << sum << endl;
    }
    return 0;
}

我首先在纸上对数组 [1,2,3,4,5,6] 进行了命中和试验方法，发现最大相邻和为 [1,3,5,6,4,2] （Baiscally max之间的值，左侧和右侧的值递减）。为此，我首先按升序排列数组 [1,2,3,4,5,6]，将其替代值存储在数组 [1,3,5] 中，然后按降序排列 [6,5 ,4,3,2,1] 并将替代值附加到使其成为 [1,3,5,6,4,2] 的数组。然后按预期打印出求和函数。该 sol 适用于测试用例 [3,6] 和 [2,2,1,2,2]

Answer 1

给定一个大小为 N (N≥2) 的数组 A。

我们定义 i=1, ..., N−1 f(A)=Σ(Ai+Ai+1)。

通过以任意顺序重新排列 A 的元素，找到 f(A) 的最大值。

所以，无论顺序如何，最终总和是：

(A1 + A2) + (A2 + A3) ... + (An-2 + An-1) + (An-1 + An)

即：

A1 + 2(A2 + A3 + ... + An-1) + An

因此，考虑到 + 是可交换和结合的，您可以通过找到两个最小的元素并将其中一个与第一个元素交换，另一个与第二个元素交换来最大化这个总和。所以：

int min, min2, minIndex = 0, minIndex2 = 1;
if (arr[0] < arr[1]) {
    min = arr[0];
    min2 = arr[1];
} else {
    min = arr[1];
    min2 = arr[0];
}
for (int i = 2; i < size; i++) {
    if (arr[i] <= min) {
        min2 = min;
        min = arr[i];
        min2Index = minIndex;
        minIndex = i;
    } else if (arr[i] < min2) {
        min2Index = i;
        min2 = arr[i];
    }
}
int swap = arr[0];
arr[0] = min;
arr[minIndex] = swap;
swap = arr[size - 1];
arr[size - 1] = min2;
arr[minIndex2] = swap;

上面的解决方案假设您至少有 2 个元素，因此您可以实现一个函数，从验证输入和处理简单情况开始，然后继续上面的延续。