水晶球 | 贪心、排序

逃离我推掉我的手 2022-12-07 04:29 184阅读 0赞
  1. 水晶球





















成绩

10

开启时间

2020年09月14日 星期一 12:00

折扣

0.8

折扣时间

2020年09月21日 星期一 00:00

允许迟交

否

关闭时间

2020年10月10日 星期六 23:00

Description

和许多同龄女孩子一样，久莲也喜欢水晶球。

还有10天，就是心心念念的他生日了。久莲希望把全世界最大最好看的水晶球送给他。她找到了宝石收藏家亚瑟斯，希望能够寻求他的帮助。亚瑟斯很快被打动了，拿出了精心收集的n块美丽的水晶石，这些水晶石初始是长宽高分别为a、b、c。亚瑟斯许诺久莲可以从中取走1块水晶石作为她礼物的原材料。

同时亚瑟斯有一种魔法，如果这两块长方形水晶石在某一个面能够完美的契合在一起（完美的契合是指这两个长方形面全等），那么可以将它们融合成一块完整的大石头，如果真的实现的话，那么久莲就可能打磨出更大的水晶球啦！

久莲太希望把最美最大的水晶球送给他了，你快帮帮她如何选择吧。

1、知识补充

  1.    首先把一些预热知识放在最前面，这道题的实现离不开排序，最重要的是对结构体的分类排序。  
  3.    你应该在学c已经学会了冒泡排序、选择排序呀啥的，不知道你忘了没，鸡翅有总结过哦，你可以复习复习。贴心送上传送门：
  5.     [选择排序][Link 1]       [插入排序][Link 2]  
  7.    但是c++的**algorithm库**里已经有实现好的**sort排序函数**，它肯定比你写的肯定更快更好，而且它可以实现很多种类别的排序：int、char...最强的是，可以对**结构体排序**。如果不熟悉sort函数的使用，一定先看看鸡翅总结的这篇文章速成一下：[排序算法 | sort函数的使用][_ sort]，再看题解，不然你可能会一脸懵嘻嘻~

2、预处理

  1.    这个题就是个很典型的贪心问题，想明白了思路就很简单。  
  3.    为了让数据方便处理，我们希望将每一个长方体的数据存放在一起（由于输出需要标示长方体，所以我们除了长宽高数据还需要记录id），那就应该用一个**结构体crystal描述长方体的数据**。所有的长方体我们需要一个**crl\[ \]的结构体数组**来储存。结构体的定义和结构体数组的声明如下：
  5. struct crystal {
  6.     long long id;  //水晶石的标号
  7.     long long length, width, height; //水晶石的长宽高
  8. } crl[MAXN];
  10.     接下来分析几点重要的：       
  12.     首先我们应该要明白，**水晶球的大小完全由长方体的最短边决定！**我们的目的就是让最短边的最长！  
  14.     那么对于一个长方体（length，width，height）为了方便处理，需要规定一下：**length > width > height**。这一步可以在处理输入的时候完成。所以在合并水晶球的时候，我们**只要选择 length \* width 这个面合并以增大最短边。其他面合并是没有意义的，因为本质上不会增大最短边！**

3.核心算法

经过预处理后，接着处理分为两部分：

1、不合并
一一遍历结构体数组中的每一个长方体，找到最大的height，记录下其对应的id（编号）。

2、合并
先对结构体数组进行排序，优先以length关键字排序，如果相同就以width为关键字排序，如果再相同就以heigjt为关键字排序。
这样排序完，length*width 面可以合并的情况就只会出现在相邻的长方体上，所以我们只需要考虑相邻长方体的合并了！大大减少了我们的讨论次数！

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

下面附上完整代码：

  1. #include <cstdio>
  2. #include <algorithm>
  4. #define MAXN 100050
  6. using namespace std;
  8. struct crystal {
  9.     long long id;  //水晶石的标号
  10.     long long length, width, height; //水晶石的长宽高
  11. } crl[MAXN];
  13. bool cmpForStruct(struct crystal x, struct crystal y) {
  14.     if (x.length != y.length)  //先按长度排序
  15.         return x.length > y.length;
  16.     else if (x.width != y.width)  //再按宽度排序
  17.         return x.width > y.width;
  18.     else
  19.         return x.height > y.height;   //最后按照高度排序
  20. }
  22. int main() {
  23.     long long n;
  24.     scanf("%lld\n", &n);
  26.     long long maxHeight = 0;  //记录水晶石的最高高度
  27.     long long x = 0, y = 0;  //记录选择水晶石的标号，当不可以合并时，只取x
  29.     for (long long i = 0; i < n; i++) {
  30.         long long temp[3];  //暂用来排序的数组
  31.         scanf("%lld%lld%lld", &temp[0], &temp[1], &temp[2]);  //将输入的长宽高先放到数组temp中
  32.         sort(temp, temp + 3);  //对temp数组[0,2]进行从小到大排序
  34.         //将输入更新到结构体数组中
  35.         crl[i].id = i + 1;
  36.         crl[i].length = temp[2];
  37.         crl[i].width = temp[1];
  38.         crl[i].height = temp[0];
  40.         //记录单个水晶石的最大高度
  41.         if (crl[i].height > maxHeight) {
  42.             maxHeight = crl[i].height;
  43.             x = crl[i].id;  //记下标号
  44.         }
  45.     }
  47.     sort(crl, crl + n, cmpForStruct);  //对水晶石结构体数组[0,n-1]进行排序，按照长、宽、高优先级排序
  49.     //依次讨论相邻水晶石合并的问题
  50.     for (long long i = 0; i < n - 1; i++) {
  51.         if (crl[i].length == crl[i + 1].length && crl[i].width == crl[i + 1].width) {
  52.             long long temp = crl[i].height + crl[i + 1].height;  //合并
  54.             //计算合并之后的最短边
  55.             if (temp > crl[i].width)
  56.                 temp = crl[i].width;
  58.             //更新两个水晶石的最大高度
  59.             if (temp > maxHeight) {
  60.                 maxHeight = temp;
  61.                 x = crl[i].id;  //记下标号,不要以为下标+1就是id，你要记得我们对结构体数组排序过....
  62.                 y = crl[i + 1].id;
  63.             }
  64.         }
  65.     }
  67.     if (y == 0)
  68.         printf("%d\n%lld\n", 1, x);
  69.     else
  70.         printf("%d\n%lld %lld\n", 2, x, y);
  73. }

end

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

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

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

在这里插入图片描述

发表评论

表情：
评论列表 （有 0 条评论，184人围观）

还没有评论，来说两句吧...

相关阅读