Kostya the Sculptor（贪心

这题本来想二分。想了很久很久，解决不了排序和二分的冲突。用贪心吧。。

题意：

　　给你n个长方形,让你找出2个或1个长方体,使得他们拼接成的长方体的内接球半径最大（这是要求最短边越大越好）（两个矩形拼接的条件是

他们有一个面完全相同）

　　输入n，输入第 i个长方体的三条边长度。最多2个长方体拼接。

　　输出不要拼接的"1"和最大能切成内切球的 i ；或者输出要拼接的“2”和这两个长方体的序号 i 。

如果两个长方体的边长分别是 3 2 4，3 2 4 。可以拼接成 6 2 4，3 2 8，3 4 4；

显然 3 4 4这种拼法内切球是最大的。（这里是想到用贪心的起点）

给所有的长方体记录原来的位置序号，再按边长排序，（下面代码里的cmp）。这样可以保证每个长方体的第三条边都是最小的，

这样两个长方体的第三条边相加起来，能使两个长方体的最短边得到加强。（类似木桶的短板原理）

 #include<iostream>

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<cmath>

 #include<string>

 #include<cmath>

 #include<set>

 #include<vector>

 #include<stack>

 #include<queue>

 #include<map>

 using namespace std;

 #define ll long long

 #define se second

 #define fi first

 const int INF= 0x3f3f3f3f;

 const int N=1e5+;

 int a[],b[];

 int n,maxn=;

 struct note

 {

     int x,y,z;

     int loc;

 }q[N];

 bool cmp(note r,note t)

 {

     return (r.x>t.x||

             r.x==t.x&&r.y>t.y||

             r.x==t.x&&r.y==t.y&&r.z>t.z);

 }

 int main() //（3 2 4 ；3 2 4）3*2*8，6*2*4，3*4*4选的是3*4*4。

 {

     cin>>n;

     int loc=,loc1=,loc2=; //这是要输出的长方体位置

     for(int i=;i<=n;i++){

         scanf("%d%d%d",&a[],&a[],&a[]);

         sort(a,a+);

         q[i].z =a[];

         q[i].y =a[];

         q[i].x =a[];

         q[i].loc =i; //记录原来的下标

         if(maxn<a[])

         {

              maxn=a[];

              loc=i;

         }

     }

     sort(q+,q++n,cmp);

     int sign=;

     for(int i=;i<n;i++)

     {

         if(q[i].x==q[i+].x && q[i].y==q[i+].y)

         {

             b[]=q[i].x; b[]=q[i].y; b[]=q[i].z+q[i+].z;

             sort(b,b+);

             if(maxn<b[])

             {

                 maxn=b[];

                 loc1=q[i].loc;

                 loc2=q[i+].loc;

                 sign=;

             }

         }

     }

     if(sign){

         cout<<<<endl;

         cout<<loc1<<' '<<loc2;

     }

     else

         cout<<<<endl<<loc;

 }

巴特西

Kostya the Sculptor（贪心

最新文章

热门文章