基于贪心算法求解数组拆分的最大与最小差值（兼容奇偶长度）

问题描述：
给定长度为n的数组A，你需要从数组中恰好移除⌊n/2⌋个元素，添加到初始为空的数组B中。求两个数组差值的最大值与最小值，两个数组的差值定义为sum(abs(A[i]-B[i]))。

原代码问题分析 #

原C++代码仅支持偶数长度数组的核心原因是：

• 最大值计算时默认数组前后两半长度相等，奇数长度时后半段起始索引偏移错误
• 最小值计算时默认可以两两配对所有元素，奇数长度时会遗漏最优配对策略

兼容奇偶长度的解决方案 #

首先对数组做升序排序，再分别调整最值的计算逻辑：

• 最大值：取前⌊n/2⌋个最小元素分到B，后⌊n/2⌋个最大元素留在A，对应位置相减求和即可，中间的冗余元素不对差值产生贡献
• 最小值：尽可能让相邻元素配对（一个在A一个在B），奇数长度时额外判断跳过首元素或者中间元素的配对情况，取最小结果

修改后代码 #

#include <bits/stdc++.h>
using namespace std;     

int main(){      
    int n;  
    cin >> n;   
    vector<int> a(n);    
    for(int i=0; i<n; i++){      
        cin >> a[i];        
    }       
    sort(a.begin(), a.end());       
    long long mn = 0, mx = 0; 
    int k = n / 2; // 对应⌊n/2⌋
    int half_ceil = (n + 1) / 2; // 对应⌈n/2⌉
    // 计算最大值
    for(int i=0; i<k; i++){    
        mx += a[i + half_ceil] - a[i];         
    }
    // 计算基础最小值：从第一个元素开始两两配对
    for(int i=0; i<k; i++){
        mn += a[2*i + 1] - a[2*i];
    }
    // 奇数长度时补充判断从第二个元素开始配对的情况，取更小值
    if(n % 2 == 1){
        long long mn_alt = 0;
        for(int i=0; i<k; i++){
            mn_alt += a[2*i + 2] - a[2*i +1];
        }
        mn = min(mn, mn_alt);
    }
    cout << mn << " " << mx << endl;
    return 0;
}

代码说明 #

• 最大值计算使用half_ceil作为后半段的起始偏移，天然兼容奇偶长度的数组
• 奇数长度时最小值计算覆盖两种配对策略，保证得到最优结果
• 所有差值计算基于排序后的数组，天然满足绝对值要求，不需要额外做绝对值转换

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