贪心：最大容量和

文章目录

贪心：最大容量和

问题：

思路：

首先我们需要知道，每个桶的容量就是组成它的最短木板的长度，要让总容量最大，那么我们所选取的每个桶的最短木板的长度也要尽可能大，于是我们的贪心策略为：尽可能让长木板作为最短木板
我们将木板按长度从小到大排序，用wood[]数组表示。每个木板都是需要用上的，最短的那根木板也需要用上，设其长度为wood[0]，而任意桶间的容量差要大于等于L，那么我们能选择的组成桶的最短木板的最大长度为wood[0] + L。我们遍历wood[]数组，找到最后一个长度小于等于wood[0] + L的木板，设其下标为pos，那么pos之后的木板都不能作为最短木板，而只能作为和最短木板配对的木板，即我们需从下标0~pos中选出n根木板作为最短板。对于我们所选择的最短木板，只有存在k – 1个大于等于其长度的木板才能配对成功组成木桶，因此我们可以用num记录用作配对的木板数量，初始值为m – pos，我们从pos开始从后向前遍历，依次判断每块最短木板是否能成功配对，若num >= k-1，则把当前木板作为最短板与num中k-1根比它长的木板配对，若num < k – 1，只能把当前木板当配对木板。配对成功，则更新num值为num – (k – 1)，配对失败，则当前木板在贪心策略下不可能构成木桶了，只能用作配对，num++。我们用count记录成功配对构成的木桶数，若count == n，则输出最大容量和。

代码：

import java.util.*;

public class Main {
    static long[] wood = new long[100002];
    public static void main(String[] args) {
        long L, ans = 0;
        int n, k, m, num, i, pos, count = 0;
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        k = scanner.nextInt();
        L = scanner.nextLong();
        m = n * k;
        for (i = 0;i < m;i++) {
            wood[i] = scanner.nextLong();
        }
        Arrays.sort(wood, 0, m);
        i = 1;
        while (i < m && wood[i] <= wood[0] + L) {
            i++;
        }
        pos = i;
        num = m - pos;
        for (i = pos - 1;i >= 0;i--) {
            if (num >= k - 1) {
                num -= (k - 1);
                ans += wood[i];
                count++;
            } else {
                num++;
            }
        }
        System.out.println(count == n ? ans : 0);
    }
}