水晶球 | 贪心、排序

逃离我推掉我的手 2022-12-07 04:29 133阅读 0赞

> 14. 水晶球
> 
> <table> 
> <tbody> 
> <tr> 
> <td> 成绩 </td> 
> <td> 10 </td> 
> <td> 开启时间 </td> 
> <td> 2020年09月14日 星期一 12:00 </td> 
> </tr> 
> <tr> 
> <td> 折扣 </td> 
> <td> 0.8 </td> 
> <td> 折扣时间 </td> 
> <td> 2020年09月21日 星期一 00:00 </td> 
> </tr> 
> <tr> 
> <td> 允许迟交 </td> 
> <td> 否 </td> 
> <td> 关闭时间 </td> 
> <td> 2020年10月10日 星期六 23:00 </td> 
> </tr> 
> </tbody> 
> </table>
> 
> **Description**
> 
> 和许多同龄女孩子一样，久莲也喜欢水晶球。
> 
> 还有10天，就是心心念念的他生日了。久莲希望把全世界最大最好看的水晶球送给他。她找到了宝石收藏家亚瑟斯，希望能够寻求他的帮助。亚瑟斯很快被打动了，拿出了精心收集的n块美丽的水晶石，这些水晶石初始是长宽高分别为a、b、c。亚瑟斯许诺久莲可以从中取走1块水晶石作为她礼物的原材料。
> 
> 同时亚瑟斯有一种魔法，如果这两块长方形水晶石在某一个面能够完美的契合在一起（完美的契合是指这两个长方形面全等），那么可以将它们融合成一块完整的大石头，如果真的实现的话，那么久莲就可能打磨出更大的水晶球啦！
> 
> 久莲太希望把最美最大的水晶球送给他了，你快帮帮她如何选择吧。

--------------------

### 1、知识补充 ###

首先把一些预热知识放在最前面，这道题的实现离不开排序，最重要的是对结构体的分类排序。  
  
       你应该在学c已经学会了冒泡排序、选择排序呀啥的，不知道你忘了没，鸡翅有总结过哦，你可以复习复习。贴心送上传送门：

[选择排序][Link 1]       [插入排序][Link 2]  
  
       但是c++的**algorithm库**里已经有实现好的**sort排序函数**，它肯定比你写的肯定更快更好，而且它可以实现很多种类别的排序：int、char...最强的是，可以对**结构体排序**。如果不熟悉sort函数的使用，一定先看看鸡翅总结的这篇文章速成一下：[排序算法 | sort函数的使用][_ sort]，再看题解，不然你可能会一脸懵嘻嘻~

### 2、预处理 ###

这个题就是个很典型的贪心问题，想明白了思路就很简单。  
  
       为了让数据方便处理，我们希望将每一个长方体的数据存放在一起（由于输出需要标示长方体，所以我们除了长宽高数据还需要记录id），那就应该用一个**结构体crystal描述长方体的数据**。所有的长方体我们需要一个**crl\[ \]的结构体数组**来储存。结构体的定义和结构体数组的声明如下：

struct crystal {
        long long id;  //水晶石的标号
        long long length, width, height; //水晶石的长宽高
    } crl[MAXN];

接下来分析几点重要的：

首先我们应该要明白，**水晶球的大小完全由长方体的最短边决定！**我们的目的就是让最短边的最长！  
  
        那么对于一个长方体（length，width，height）为了方便处理，需要规定一下：**length > width > height**。这一步可以在处理输入的时候完成。所以在合并水晶球的时候，我们**只要选择 length \* width 这个面合并以增大最短边。其他面合并是没有意义的，因为本质上不会增大最短边！**

### 3.核心算法 ###

经过预处理后，接着处理分为两部分：  
  
**1、不合并**  
        一一遍历结构体数组中的每一个长方体，找到最大的height，记录下其对应的id（编号）。  
  
**2、合并**  
       先对结构体数组进行排序，优先以length关键字排序，如果相同就以width为关键字排序，如果再相同就以heigjt为关键字排序。  
       这样排序完，length\*width 面**可以合并的情况就只会出现在相邻的长方体上**，所以我们只需要考虑相邻长方体的合并了！大大减少了我们的讨论次数！

接下来我们一一枚举相邻的长方体是否能合并：如果能合并，计算合并后的最短边。如果比当前最长最短边还要长，则更新最长最短边，并留下对应的两个id。  
  
        比如长方体A1（length，width，height1）和 长方体A2（length, width, height2）的合并结果为：（length，width，height1+height2）。注意，**合并之后的最短边为：min（width， height1+height2）**。

--------------------

下面附上完整代码：

#include <cstdio>
 #include <algorithm>
 
 #define MAXN 100050
 
 using namespace std;
 
 struct crystal {
 long long id; //水晶石的标号
 long long length, width, height; //水晶石的长宽高
 } crl[MAXN];
 
 bool cmpForStruct(struct crystal x, struct crystal y) {
 if (x.length != y.length) //先按长度排序
 return x.length > y.length;
 else if (x.width != y.width) //再按宽度排序
 return x.width > y.width;
 else
 return x.height > y.height; //最后按照高度排序
 }
 
 int main() {
 long long n;
 scanf("%lld\n", &n);
 
 long long maxHeight = 0; //记录水晶石的最高高度
 long long x = 0, y = 0; //记录选择水晶石的标号，当不可以合并时，只取x
 
 for (long long i = 0; i < n; i++) {
 long long temp[3]; //暂用来排序的数组
 scanf("%lld%lld%lld", &temp[0], &temp[1], &temp[2]); //将输入的长宽高先放到数组temp中
 sort(temp, temp + 3); //对temp数组[0,2]进行从小到大排序
 
 //将输入更新到结构体数组中
 crl[i].id = i + 1;
 crl[i].length = temp[2];
 crl[i].width = temp[1];
 crl[i].height = temp[0];
 
 //记录单个水晶石的最大高度
 if (crl[i].height > maxHeight) {
 maxHeight = crl[i].height;
 x = crl[i].id; //记下标号
 }
 }
 
 sort(crl, crl + n, cmpForStruct); //对水晶石结构体数组[0,n-1]进行排序，按照长、宽、高优先级排序
 
 //依次讨论相邻水晶石合并的问题
 for (long long i = 0; i < n - 1; i++) {
 if (crl[i].length == crl[i + 1].length && crl[i].width == crl[i + 1].width) {
 long long temp = crl[i].height + crl[i + 1].height; //合并
 
 //计算合并之后的最短边
 if (temp > crl[i].width)
 temp = crl[i].width;
 
 //更新两个水晶石的最大高度
 if (temp > maxHeight) {
 maxHeight = temp;
 x = crl[i].id; //记下标号,不要以为下标+1就是id，你要记得我们对结构体数组排序过....
 y = crl[i + 1].id;
 }
 }
 }
 
 if (y == 0)
 printf("%d\n%lld\n", 1, x);
 else
 printf("%d\n%lld %lld\n", 2, x, y);
 
 
 }

--------------------

# end  #

欢迎关注个人公众号**“** **鸡翅编程 ”**，这里是认真且乖巧的码农一枚。

*---- 做最乖巧的博客er，做最扎实的程序员 ----*

旨在用心写好每一篇文章，平常会把笔记汇总成推送更新~

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

[Link 1]: https://blog.csdn.net/weixin_43787043/article/details/104264825
[Link 2]: https://blog.csdn.net/weixin_43787043/article/details/104266027
[_ sort]: https://blog.csdn.net/weixin_43787043/article/details/104267119
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4NzA0Mw_size_16_color_FFFFFF_t_70]: /images/20221123/16bdaeba6832441aa0796d18c2eceee1.png