集合框架题：PIPI的乐高积木

我不是女神ヾ 2023-10-06 19:21 14阅读 0赞

## 集合框架题：PIPI的乐高积木 ##

#### 问题： ####

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bem6IGM5paw5omL_size_20_color_FFFFFF_t_70_g_se_x_16]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bem6IGM5paw5omL_size_19_color_FFFFFF_t_70_g_se_x_16]

#### 思路： ####

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bem6IGM5paw5omL_size_20_color_FFFFFF_t_70_g_se_x_16 1]  
首先，为了保证最高柱子与最矮柱子的高度差越来越小，每次移动都需要将最高柱子上的一个块移动到最矮柱子上，即最矮柱子高度 + 1，最高柱子高度 - 1。我们需要一种数据结构能使其中的元素一直保持按序排列，红黑树即是我们需要的数据结构，Java中TreeSet即是用红黑树实现的，能满足上述要求。

对于高度的变化，我们只需删除原来最高柱与最矮柱，然后添加两个新柱子即可，高度分别为最矮柱子高度 + 1，最高柱子高度 - 1

由于最后需要输出每次移动的两个柱子的编号，我们还需将编号和高度一同存入TreeSet。每次移动的柱子的编号存入二维数组中即可。

**需注意的点**：

*  当最高柱高度 - 最矮柱高度 <= 1时，此时已无法再减少两者之差，因此终止移动
 *  当高度相同时，我们需选取编号最大的高柱和编号最小的矮柱。创建类保存编号和高度，该类需实现Comparable接口，重写compareTo方法自定义排序规则

#### 代码： ####

import java.util.Scanner;
    import java.util.TreeSet;
    
    public class Main {
        
        static TreeSet<HeightAndNum> treeSet = new TreeSet<>();
        public static void main(String[] args) {
        
            int move[][] = new int[5005][2];
            int minBeauty;
            Scanner scanner = new Scanner(System.in);
            int N = scanner.nextInt();
            int k = scanner.nextInt();
            int i;
            for (i = 0;i < N;i++) {
        
                treeSet.add(new HeightAndNum(scanner.nextInt(), i + 1));
            }
            i = 0;
            while (i < k) {
        
                if (treeSet.last().height - treeSet.first().height <= 1) {
        
                    break;
                }
                int minNum = treeSet.first().num;
                int maxNum = treeSet.last().num;
                int minPoll = treeSet.pollFirst().height;
                int maxPoll = treeSet.pollLast().height;
                treeSet.add(new HeightAndNum(minPoll + 1, minNum));
                treeSet.add(new HeightAndNum(maxPoll - 1,maxNum));
                move[i][0] = maxNum;
                move[i][1] = minNum;
                i++;
            }
            minBeauty = treeSet.last().height - treeSet.first().height;
            System.out.print(minBeauty + " " + i);
            System.out.print('\n');
            for (int j = 0;j < i;j++) {
        
                System.out.println(move[j][0] + " " + move[j][1]);
            }
        }
    
        static class HeightAndNum implements Comparable{
        
            int height;
            int num;
            public HeightAndNum(int height, int num) {
        
                this.height = height;
                this.num = num;
            }
    
            @Override
            public int compareTo(Object o) {
        
                HeightAndNum other = (HeightAndNum) o;
                if (this.height > other.height) {
        
                    return 1;
                } else if (this.height == other.height) {
        
                    return this.num - other.num;
                }
                return -1;
            }
        }
    }

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bem6IGM5paw5omL_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/ee14d5bf2d8e4629b17461fce598cfad.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA5bem6IGM5paw5omL,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bem6IGM5paw5omL_size_19_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/c16c3ab6bab84f2d88d2a3936a44884c.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA5bem6IGM5paw5omL,size_19,color_FFFFFF,t_70,g_se,x_16
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bem6IGM5paw5omL_size_20_color_FFFFFF_t_70_g_se_x_16 1]: https://img-blog.csdnimg.cn/de6ef067dc824202bda1dc0f875bdfc0.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA5bem6IGM5paw5omL,size_20,color_FFFFFF,t_70,g_se,x_16