题目描述

难度分:$1500$

输入$n$，$k(1 \leq n,k \leq 10^5$且$1 \leq n \times k \leq 10^5)$，$L(0 \leq L \leq 10^9)$和长为$n \times k$的数组$a(1 \leq a[i] \leq 10^9)$，表示$n \times k$条木板的长度。

你要制作$n$个木桶，每个木桶需要$k$条木板。你可以使用任意$k$条木板来组装一个木桶，每条木板必须恰好属于一个木桶。一个木桶的体积，等于其最短木板的长度。

要求：任意一对木桶的体积差都不能超过$L$。输出所有木桶体积和的最大值。如果无法满足，输出$0$。

输入样例$1$

4 2 1
2 2 1 2 3 2 2 3

输出样例$1$

7

输入样例$2$

2 1 0
10 10

输出样例$2$

20

输入样例$3$

1 2 1
5 2

输出样例$3$

2

输入样例$4$

3 2 1
1 2 3 4 5 6

输出样例$4$

0

算法

贪心

很不擅长做这种贪心题，WA了好多发，就是手残写不对。

首先将$a$数组排序，可以知道$a[1]$是肯定要选的，因为一定有一个桶是以$a[1]$为最短板。二分找到最后一个满足$a[p]-a[1] \leq L$的$p$，每次选择最后$k-1$个木条（假设最后一个位置$ed=n \times k$）和$a[j]$匹配（初始情况下$j=p$），造一个体积为$a[j]$的桶，然后$j=j-1$，$ed=ed-(k-1)$。

在这个过程中用一个$cnt$变量记录已经有多少个桶了，一旦发现$ed-(k-1) \leq p$了，说明$a[j]$作为桶的体积就太大了，后面不够$k-1$个长度不小于它的木条了，退出从后往前贪的过程。然后从前往后贪，从$1$开始，步长为$k$把剩下的$n-cnt$个桶的体积贪完即可。

感觉是一道很有水平的贪心题，有思维难度，也有代码实现难度。

复杂度分析

时间复杂度

后续的贪心过程时间复杂度是线性的，瓶颈在于前面的排序过程，时间复杂度为$O(nklog_2nk)$。

空间复杂度

除了输入的数组$a$，整个过程仅使用了有限几个变量，因此空间复杂度由排序决定。以快排为基准，算法的额外空间复杂度为$O(log_2nk)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;

const int N = 100010;
int n, k, l, a[N];

int main() {
    scanf("%d%d%d", &n, &k, &l);
    int m = n*k;
    for(int i = 1; i <= m; i++) {
        scanf("%d", &a[i]);
    }
    sort(a + 1, a + m + 1);
    int p = upper_bound(a + 1, a + m + 1, a[1] + l) - a - 1;
    if(p < n) {
        puts("0");
        return 0;
    }
    LL ans = 0;
    int cnt = 0, j = p;
    for(int i = m; i - (k - 1) > p; i -= k - 1) {
        ans += a[j--];
        cnt++;
    }
    for(int i = 1; i <= p - cnt; i += k) {
        ans += a[i];
    }
    printf("%lld\n", ans);
    return 0;
}