贪心：最大容量和

分手后的思念是犯贱 2023-10-06 20:23 16阅读 0赞

## 贪心：最大容量和 ##

#### 文章目录 ####

*  贪心：最大容量和
 *   *   *  问题：
         *  思路：
         *  代码：

#### 问题： ####

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bCP54G15a6d_size_20_color_FFFFFF_t_70_g_se_x_16]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bCP54G15a6d_size_20_color_FFFFFF_t_70_g_se_x_16 1]

#### 思路： ####

首先我们需要知道，每个桶的容量就是组成它的最短木板的长度，要让总容量最大，那么我们所选取的每个桶的最短木板的长度也要尽可能大，于是我们的贪心策略为：尽可能让长木板作为最短木板  
  我们将木板按长度从小到大排序，用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);
        }
    }

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bCP54G15a6d_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/89caceb13b8b48efad070289c3492f72.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA5bCP54G15a6d,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bCP54G15a6d_size_20_color_FFFFFF_t_70_g_se_x_16 1]: https://img-blog.csdnimg.cn/cf46d1daba8f457790010526f56d05d9.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA5bCP54G15a6d,size_20,color_FFFFFF,t_70,g_se,x_16