[C++知识库]BIT大二计科小学期-程设-水晶球

?题目：

?

?测试用例：

AC代码：?

#include <stdio.h>
#include <stdlib.h>//包含了qsort函数，格式为void qsort(void* base,size_t num,size_t width,int(__cdecl*compare)(const void*,const void*));  
#define MAX 100050
 
 
struct struction {
    long long id;  //水晶石的标号
    long long a;//长
	long long b;//宽 
	long long c;//高 
};

struct struction a[MAX];//存储输入数据 

//用C语言实现按照不同的优先级快速排序，实际上用C++更省事，但是爷就要强行C
int cmp_a(const void *a,const void *b)//函数的格式是qsort规定的，返回值<0,a在b前，反之b在a前，等于0则不变  
{
	struct struction *aa=(struct struction*)a;struct struction *bb=(struct struction*)b;//强制类型转换 
	return ((aa->a<bb->a)?1:-1);
}
int cmp_b(const void *a,const void *b)
{
	struct struction *aa=(struct struction*)a;struct struction *bb=(struct struction*)b;
	return ((aa->b<bb->b)?1:-1);
}
int cmp_c(const void *a,const void *b)
{
	struct struction *aa=(struct struction*)a;struct struction *bb=(struct struction*)b;
	return ((aa->c<bb->c)?1:-1);
}
void Sort(struct struction *a,int n)//先排a,再排b,最后c（全部降序） 
{
	long long i,k=0,start1=0,start2,flag=0;
	qsort(a,n,sizeof(struct struction),cmp_a);
	for(i=0;i<n-1;i++)
	{
		if(a[i].a!=a[i+1].a)
		{
			flag=1;
			qsort(a+start1,i-start1+1,sizeof(struct struction),cmp_b);
			start2=start1;
			{
				for(k=start1;k<i-start1+1;k++)
				{
					if(a[k].b!=a[k+1].b)
					{
						qsort(a+start2,k-start2+1,sizeof(struct struction),cmp_c);
						start2=k+1;
					}
				}
			}
			start1=i+1;
		}
		
	}
	if(flag==0)
	{
		flag=0;
		start1=0;
		qsort(a,n,sizeof(struct struction),cmp_b);
		for(i=0;i<n-1;i++)
		{
			if(a[i].b!=a[i+1].b)
			{
				flag=1;
				qsort(a+start1,i-start1+1,sizeof(struct struction),cmp_c);
				start1=i+1;
			}
		}
		if(flag==0) qsort(a,n,sizeof(struct struction),cmp_c);
		
	}
	
}

void paixu(long long a[])//简单地对temp排序，排出长宽高 
{
	int i,j;
	long long t;
	for(i=0;i<2;i++)
	for(j=i;j<3;j++)
	{
		if(a[i]>a[j])
		{
			t=a[i]; a[i]=a[j]; a[j]=t;
		}
	}
	return;
}
 
int main() {
    long long n,i;
    scanf("%lld\n", &n);
 
    long long maxHeight = 0;  //记录水晶石的最高高度
    long long x = 0, y = 0;  //记录选择水晶石的标号，当不可以合并时，只取x
 
    for (i = 0; i < n; i++) 
	{
        long long temp[3];  //暂用来排序的数组
        scanf("%lld %lld %lld", &temp[0], &temp[1], &temp[2]);  //将输入的长宽高先放到数组temp中
        paixu(temp);  //对temp数组[0,2]进行从小到大排序，这里规定长>宽>高，便于进行后面的贪心 
 
        //将每一组排好的长宽高输入到结构体数组中
        a[i].id = i + 1;
        a[i].a = temp[2];
        a[i].b = temp[1];
        a[i].c = temp[0];
 
        //考察这些水晶石的最长的最短边是多少（绕口令了属于是） 
        if (a[i].c > maxHeight) {
            maxHeight = a[i].c;
            x = a[i].id;  //记下对应的index
        }
    }
 
    Sort(a,n);  //对水晶石结构体数组[0,n-1]进行排序，按照长、宽、高优先级排序
    
 
    //依次讨论相邻水晶石合并的问题(贪心) 
    for (i = 0; i < n - 1; i++) 
	{
        if (a[i].a == a[i + 1].a && a[i].b == a[i + 1].b) //由于水晶球的半径取决于最短边的长，应优先使两个水晶最短边合并，因此排序过后仅考察两个较长边相等时的情况 
		{
            long long temp = a[i].c + a[i + 1].c;
 
            //两个最短边合并之后如果比宽长，最短边就变为宽 
            if (temp > a[i].b) temp = a[i].b;
 
            //更新这些水晶石的最长的最短边 
            if (temp > maxHeight) 
			{
                maxHeight = temp;
                x = a[i].id;  //记下index
                y = a[i + 1].id;
            }
        }
    }
    if (y == 0)
        printf("%d\n%lld\n", 1, x);
    else
        {
        	if(x<y) printf("%d\n%lld %lld\n", 2, x, y);
        	else printf("%d\n%lld %lld\n", 2, y, x);
		}
 
 
}