Description 给出若干长方体形状石头的边长，可以从中至多选出两块石头组成一块新石头（被选出的两块石头必须有一面一样这样才能组成一块新的长方体石头），然后把这个长方体石头切成最大的正方体石头，问能够切出的最大正方体石头的边长 Input 第一行一整数n表示石头数量，之后n行每行三个整数a[i],b[i],c[i]表示一块石头的三个边长(1<=n<=1e5,1<=a[i],b[i],c[i]<=1e9) Output 输出选出的石头数量以及能够切出的正方体石头边长 Sample Input 6 5 5 5 3 2 4 1 4 1 2 1 3 3 2 4 3 3 4 Sample Output 1 1 Solution 选一块的话边长就是这n块石头每块三条边最小值中的最大值，选两块的话，如果是拿两块石头的较小面贴在一起形成一块新石头，即最短边是重合面的边的话，那么新石头能够刻出的最大正方形边长也最多是最短边的长度，而这个长度在选一块石头的时候已经被考虑了，此处考虑这类方案毫无意义，所以只需要考虑两个较长边是否可以合成一个面然后通过把两块石头的最短边连成一个较长边来得到更优的解即可，那么先把每块石头的三条边按长度降序排，然后把这n个石头按最长边，次长边，最短边为第一第二第三关键字排序，那么最优方案只会出现在排完序后相邻的石头之间，O(n)扫一遍即可 Code
#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> #include<cmath> #include<vector> #include<queue> #include<map> #include<set> #include<ctime> using namespace std; typedef long long ll; #define INF 0x3f3f3f3f #define maxn 100005 #define mod 1000000001ll int n; struct node { int x,y,z,id; bool operator<(const node&b)const { if(x!=b.x)return x<b.x; if(y!=b.y)return y<b.y; return z<b.z; } }a[maxn]; int main() { while(~scanf("%d",&n)) { int num=1,ans=-1,ans1,ans2; for(int i=1;i<=n;i++) { int x[4]; for(int j=0;j<3;j++)scanf("%d",&x[j]); sort(x,x+3); a[i].x=x[2],a[i].y=x[1],a[i].z=x[0],a[i].id=i; if(x[0]>ans)ans=x[0],ans1=i; } sort(a+1,a+n+1); for(int i=1;i<n;i++) if(a[i].x==a[i+1].x&&a[i].y==a[i+1].y) { int x=a[i].x,y=a[i].y,z=a[i].z+a[i+1].z; int temp=min(x,min(y,z)); if(temp>ans)num=2,ans=temp,ans1=a[i].id,ans2=a[i+1].id; } printf("%d\n",num); if(num==1)printf("%d\n",ans1); else printf("%d %d\n",ans1,ans2); } return 0; }