水晶球

admin管理员组

文章数量:1794759

水晶球

一、题目描述 

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

还有 10 天，就是心心念念的他生日了。

久莲希望把全世界最大最好看的水晶球送给他。

她找到了宝石收藏家亚瑟斯，希望能够寻求他的帮助。

亚瑟斯很快被打动了，拿出了精心收集的 n 块美丽的水晶石，这些水晶石初始是长宽高分别为 a，b ，c 的长方体。亚瑟斯许诺久莲可以从中取走 1 块水晶石作为她礼物的原材料。

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

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

Input
第一行输入一个正整数 n（1 ≤ n ≤ 1e5）；

接下来 n 行中，第 i 行输入三个正整数，表示第 i 块水晶石的长宽高。注意可能有两个长得一模一样的水晶石，但是在这种情况下还是将它们视作是两块不同的水晶石。

Output
第一行请输出一个正整数 k （1 ≤ k ≤ 2）空格，表示久莲选择的水晶球数量。

第二行请输出 k 个正整数，如果 k = 1，请输出一个正整数 x（1 ≤ x ≤ n）表示久莲选择的水晶石。如果 k = 2，则请输出两个正整数 x , y （1 ≤ x , y ≤ n）（用空格间隔），表示久莲希望亚瑟斯帮她将编号为 x 和 y 的水晶石融合成一块更大的水晶石，并选择用这块水晶石来打磨加工。请注意，这两块水晶石必须满足 “完美契合” 的条件，否则这个选择不合法。如果有多种最优的选择，则你可以输出任意一种合法的最优方案。

Hint
对于样例，如果久莲选择第六个水晶球，那么她可以打磨成半径为 r = 2.5 的水晶球，这是最优的选择。

	测试输入	期待的输出	时间限制	内存限制	额外进程
测试用例 1	以文本方式显示 6↵ 1 2 3↵ 4 1 1↵ 4 2 3↵ 4 2 3↵ 4 3 3↵ 5 5 5↵	以文本方式显示 1↵ 6↵	1秒	64M	0

 二、思路

        这道题目的关键是结构块的排序。

        首先对单块水晶块，它的外形是长方体，它的长宽高从不同的角度去看就不是单一的。例如一块3×4×5的长方体，我们也可以说它是3×5×4，也可以说是5×4×3.....因此就必须考虑到就算两块水晶块实际上长得一模一样，但是题目读入的时候也可能按照不同的顺序输入。要想方便处理这些数据，我将其统一按照长x>宽y>高z的顺序排列。

        在上述x>y>z的基础上再对不同的水晶块排列就很容易了。最终的形式应该是这样的：

 三、代码实现

定义结构体：

//定义结构体和比较函数
typedef struct crystal {int id,x,y,z;
} ctal;
//id是水晶球的序号，x、y、z是长、宽、高。bool cmp(ctal a,ctal b)
{if (a.x!=b.x) {return a.x>b.x;}else if (a.y!=b.y) {return a.y>b.y;}else {return a.z>b.z;}
}

读入和排序：

int n;
cin >> n;ctal a[n];
for ( int i=0 ; i<n ; i++ ) {a[i].id = i+1;cin >> a[i].x >> a[i].y >> a[i].z;//下面五行代码实现长宽高的排序int sum , max , min ;sum = a[i].x + a[i].y + a[i].z;max = ( max = a[i].x > a[i].y ? a[i].x : a[i].y ) > a[i].z ? max : a[i].z;min = ( min = a[i].x < a[i].y ? a[i].x : a[i].y ) < a[i].z ? min : a[i].z;a[i].x = max;a[i].z = min;a[i].y = sum - max - min;
}//使用sort函数实现对结构体的排序
sort( a , a+n , cmp );

接下来分情况讨论，如果只用一个水晶块来制作水晶球：

//如果只选择一个水晶，选择的水晶是第c1块，能制作的最大半径是d1.int c1,d1=0;
{for ( int i=0 ; i<n ; i++ ) {
//水晶球的最大半径由水晶块的高决定if ( a[i].z > d1 ) {c1 = i;d1 = a[i].z;}}
}

如果用两个水晶块来制作水晶球：

//如果选择的是两个水晶,两个选择的水晶分别是c1和c2，合并成的水晶能够做成直径为d2的水晶球int c2 , d2=0;
{int d = 0;for ( int i=0 ; i<n-1 ; i++ ) {
//如果两个水晶块长和宽都一致，就可以考虑合并它们的高，并且比较原宽和新高哪个更小，哪个就是最大半径if ( a[i].x==a[i+1].x && a[i].y==a[i+1].y ) {d = a[i].y < (a[i].z+a[i+1].z) ? a[i].y : (a[i].z+a[i+1].z);if ( d2 < d ) {c2 = i;d2 = d;}}}
}

最后只需要比较d1和d2哪个更大，哪个就是更优解，用if语句来输出。

四、完整代码

#include<bits/stdc++.h> 
using namespace std;typedef struct crystal {int id,x,y,z;
} ctal;bool cmp(ctal a,ctal b)
{if (a.x!=b.x) {return a.x>b.x;}else if (a.y!=b.y) {return a.y>b.y;}else {return a.z>b.z;}
}int main(){int n;cin >> n;ctal a[n];for (int i=0;i<n;i++) {a[i].id=i+1;cin >> a[i].x >> a[i].y >> a[i].z;int max,min,sum;sum = a[i].x + a[i].y + a[i].z;max = (max = a[i].x > a[i].y ? a[i].x : a[i].y) > a[i].z ? max : a[i].z;min = (min = a[i].x < a[i].y ? a[i].x : a[i].y) < a[i].z ? min : a[i].z;a[i].x=max; a[i].z=min; a[i].y=sum-max-min;}sort(a,a+n,cmp);//如果只选择一个水晶int c1,d1=0;
{for (int i=0;i<n;i++) {if (a[i].z>d1) {c1=i;d1=a[i].z;}}
}//如果选择的是两个水晶,两个选择的水晶分别是c1和c2，合并成的水晶能够做成直径为d2的水晶球int c2,d2=0;
{int d=0;for (int i=0;i<n-1;i++) {if ( a[i].x==a[i+1].x && a[i].y==a[i+1].y ) {d = a[i].y < (a[i].z+a[i+1].z) ? a[i].y : (a[i].z+a[i+1].z);if (d2<d) {c2=i;d2=d;}}}
}if (d1>d2) {cout << '1' << endl;cout << a[c1].id << endl;}else {cout << '2' << endl;cout << a[c2].id << ' ' << a[c2+1].id << endl;}return 0;
}

本文标签： 水晶球