题解 | #公平划分#

解题思路

这是一个数组划分问题，目标是将 个数字分成两组 个和 个)，使得两组数字之间的差值之和最小。主要思路如下：

1. 首先将数组前 个元素作为第一组，剩余元素作为第二组
2. 通过不断交换两组之间的元素，计算新的差值和
3. 如果交换后的差值和更小，则保留交换结果；否则恢复原状
4. 遍历所有可能的交换组合，找到最小的差值和

代码

#include <iostream>
#include <cmath>
using namespace std;

int L1, L2;
int getValue(int b1[], int b2[]) {
    int i, j, s(0);
    for (i = 0; i < L1; i++) {
        for (j = 0; j < L2; j++)
            s += abs(b1[i] - b2[j]);
    }
    return s;
}

int main() {
    int N, k, c;
    int i, j, m, min, smin(0);
    cin >> N >> k;
    int* a = new int[N];
    for (i = 0; i < N; i++)
        cin >> a[i];
    
    L1 = k;
    L2 = N-k;
    int* b1 = new int[L1];
    int* b2 = new int[L2];
    
    // 初始划分
    for (j = 0; j < k; j++)
        b1[j] = a[j];
    for (j = k; j < N; j++)
        b2[j-k] = a[j];
        
    smin = getValue(b1, b2);
    
    // 尝试所有可能的交换
    for (j = 0; j < k; j++)
        for (c = 0; c < N-k; c++) {
            m = b1[j];
            b1[j] = b2[c];
            b2[c] = m;
            min = getValue(b1, b2);
            if (min < smin)
                smin = min;
            else {
                b2[c] = b1[j];
                b1[j] = m;
            }
        }
    cout << smin;
    return 0;
}

import java.util.*;

public class Main {
    static int L1, L2;
    
    static int getValue(int[] b1, int[] b2) {
        int s = 0;
        for (int i = 0; i < L1; i++) {
            for (int j = 0; j < L2; j++)
                s += Math.abs(b1[i] - b2[j]);
        }
        return s;
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int k = sc.nextInt();
        
        int[] a = new int[N];
        for (int i = 0; i < N; i++)
            a[i] = sc.nextInt();
            
        L1 = k;
        L2 = N-k;
        int[] b1 = new int[L1];
        int[] b2 = new int[L2];
        
        for (int j = 0; j < k; j++)
            b1[j] = a[j];
        for (int j = k; j < N; j++)
            b2[j-k] = a[j];
            
        int smin = getValue(b1, b2);
        
        for (int j = 0; j < k; j++) {
            for (int c = 0; c < N-k; c++) {
                int m = b1[j];
                b1[j] = b2[c];
                b2[c] = m;
                int min = getValue(b1, b2);
                if (min < smin)
                    smin = min;
                else {
                    b2[c] = b1[j];
                    b1[j] = m;
                }
            }
        }
        System.out.println(smin);
    }
}

def get_value(b1, b2, L1, L2):
    s = 0
    for i in range(L1):
        for j in range(L2):
            s += abs(b1[i] - b2[j])
    return s

N, k = map(int, input().split())
a = list(map(int, input().split()))

L1 = k
L2 = N-k

b1 = a[:k]
b2 = a[k:]

smin = get_value(b1, b2, L1, L2)

for j in range(k):
    for c in range(N-k):
        b1[j], b2[c] = b2[c], b1[j]
        min_val = get_value(b1, b2, L1, L2)
        if min_val < smin:
            smin = min_val
        else:
            b1[j], b2[c] = b2[c], b1[j]

print(smin)

算法及复杂度

• 算法：贪心算法，通过不断交换元素寻找最优解
• 时间复杂度： - 外层循环 ，getValue函数
• 空间复杂度： - 需要存储原始数组和两个分组数组