方法思路

1. 设小苯选择的两堆糖果数量为a[i]和a[j]，总糖果数为sum
2. 小苯获得的糖果数量为x = a[i] + a[j]，经过乘法后变为k*x
3. 格格获得的糖果数量为y = sum - x
4. 我们需要最小化|kx - y| = |k(a[i] + a[j]) - (sum - a[i] - a[j])|
5. 化简得：|(k+1)*(a[i] + a[j]) - sum|
6. 我们可以先对数组排序，然后枚举第一堆糖果a[i]
7. 对于每个a[i]，我们需要找到最优的a[j]使|(k+1)*(a[i] + a[j]) - sum|最小
8. 如果a[i]*k已经大于等于sum-a[i]，则最优的选择是最小的糖果堆
9. 否则，我们使用二分查找找到最接近目标值的a[j]
10. 目标值可以通过求解(k+1)*(a[i] + a[j]) = sum得到，即a[j] = sum/(k+1) - a[i]
11. 我们需要找到第一个大于等于目标值的元素和第一个小于目标值的元素，比较这两个选择的差值

代码实现

Java

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] line = br.readLine().split(" ");
        int n = Integer.parseInt(line[0]);
        long k = Long.parseLong(line[1]);
        
        int[] nums = new int[n];
        line = br.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            nums[i] = Integer.parseInt(line[i]);
        }
        
        System.out.println(minDifference(n, k, nums));
    }
    
    private static long minDifference(int n, long k, int[] nums) {
        Arrays.sort(nums);
        
        long total = 0;
        for (int num : nums) {
            total += num;
        }
        
        long minDiff = Long.MAX_VALUE;
        
        for (int i = 0; i < n; i++) {
            long t = nums[i];
            
            // 如果当前数乘k已经大于等于剩余部分，选择最小的数作为第二堆
            if (t * k >= total - t && i != 0) {
                minDiff = Math.min(minDiff, Math.abs((nums[0] + t) * (k + 1) - total));
            }
            
            // 计算目标值
            long target = total - (k + 1) * t;
            
            // 二分查找最优的第二堆糖果
            int left = i + 1, right = n - 1;
            while (left <= right) {
                int mid = (left + right) >>> 1;
                if (1L * nums[mid] * k >= target - nums[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
            int p = left;
            
            // 检查右侧候选值
            if (p < n) {
                minDiff = Math.min(minDiff, Math.abs((t + nums[p]) * (k + 1) - total));
            }
            
            // 检查左侧候选值
            int q = p - 1;
            if (q >= i + 1) {
                minDiff = Math.min(minDiff, Math.abs((t + nums[q]) * (k + 1) - total));
            }
        }
        
        return minDiff;
    }
}

Python

def min_difference(n, k, nums):
    nums.sort()
    total = sum(nums)
    min_diff = float('inf')
    
    # 二分查找函数，找到第一个满足条件的位置
    def lower_bound(target, start):
        left, right = start, n - 1
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] * k >= target - nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        return left
    
    for i in range(n):
        t = nums[i]
        
        # 如果当前数乘k已经大于等于剩余部分，选择最小的数作为第二堆
        if t * k >= total - t and i != 0:
            min_diff = min(min_diff, abs((nums[0] + t) * (k + 1) - total))
        
        # 二分查找最优的第二堆糖果
        p = lower_bound(total - (k + 1) * t, i + 1)
        
        # 检查右侧候选值
        right_diff = float('inf')
        if p < n and p != i:
            right_diff = abs((t + nums[p]) * (k + 1) - total)
        
        # 检查左侧候选值
        left_diff = float('inf')
        q = p - 1
        if q >= 0 and q != i:
            left_diff = abs((t + nums[q]) * (k + 1) - total)
        
        # 更新最小差值
        min_diff = min(min_diff, left_diff, right_diff)
    
    return min_diff

# 读取输入
n, k = map(int, input().split())
nums = list(map(int, input().split()))

# 输出结果
print(min_difference(n, k, nums))

C++

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <climits>
using namespace std;

long long minDifference(int n, long long k, vector<int>& nums) {
    sort(nums.begin(), nums.end());
    
    long long total = accumulate(nums.begin(), nums.end(), 0LL);
    long long minDiff = LLONG_MAX;
    
    // 二分查找函数，找到第一个满足条件的位置
    auto lowerBound = [&](long long target, int start) {
        int left = start, right = n - 1;
        while (left <= right) {
            int mid = (left + right) >> 1;
            long long nt = target - nums[mid];
            if (1LL * nums[mid] * k >= nt) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return left;
    };
    
    for (int i = 0; i < n; i++) {
        long long t = nums[i];
        
        // 如果当前数乘k已经大于等于剩余部分，选择最小的数作为第二堆
        if (t * k >= total - t && i != 0) {
            minDiff = min(minDiff, abs((nums[0] + t) * (k + 1) - total));
        }
        
        // 二分查找最优的第二堆糖果
        int p = lowerBound(total - (k + 1) * t, i + 1);
        
        // 检查右侧候选值
        long long rightDiff = LLONG_MAX;
        if (p < n && p != i) {
            rightDiff = abs((t + nums[p]) * (k + 1) - total);
        }
        
        // 检查左侧候选值
        long long leftDiff = LLONG_MAX;
        int q = p - 1;
        if (q >= 0 && q != i) {
            leftDiff = abs((t + nums[q]) * (k + 1) - total);
        }
        
        // 更新最小差值
        minDiff = min({minDiff, leftDiff, rightDiff});
    }
    
    return minDiff;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, k;
    cin >> n >> k;
    
    vector<int> nums(n);
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }
    
    cout << minDifference(n, k, nums) << endl;
    
    return 0;
}