蒟蒻求助,80pts最后两个测试点tle,2.2s
查看原帖
蒟蒻求助,80pts最后两个测试点tle,2.2s
234344
NineQueen楼主2022/10/26 16:14
#include<bits/stdc++.h>
#define MaxN 500010
using namespace std;
int n;
struct node{
	int r;
	int nums[2];
	int p;
}point[MaxN];
bool cmp1(node a,node b){
	return a.r > b.r;
}
inline bool cs(node a,node b){
	if(a.nums[0]==b.nums[0]&&a.nums[1]==b.nums[1]) return true;
	return false;
}
inline int fun(int r){
	return r*r*r/4;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
	cin >> n;
	for(int i =1;i<=n;i++){
		int a,b,c;
		cin >> a >> b >> c;
		int minr = min(min(a,b),c);
		int maxr = max(max(a,b),c);
		point[i].p = i;
		point[i].r = minr;
		point[i].nums[0] = a+b+c-minr-maxr;
		point[i].nums[1] = maxr;
	}
	sort(point+1,point+1+n,cmp1);
	int totr = point[1].r;
	bool opt = false;
	int rank1,rank2;
	for(int i = 1;i<=n;i++){
		if(totr>=point[i].r*2) break;
		for(int j = i+1;j<=n;j++){
			if(cs(point[i],point[j])){
				int newr = point[i].r + point[j].r;
				newr = min(newr,min(point[i].nums[0],point[i].nums[1]));
				if(newr>totr){
					totr = newr;
					opt = true;
					rank1 = point[i].p;
					rank2 = point[j].p;
				}
				break;
			}
		}
	}
	cout << opt << endl;
	if(!opt){
		cout << point[1].p<<endl;
		cout << fun(point[1].r);
	}else{
		cout << rank1 <<' ' << rank2<<endl;
		cout << fun(totr);
	}
	return 0;
}

感觉不应该啊,个人认为比较重要都两个剪枝都剪了,求助大佬,谢谢

2022/10/26 16:14
加载中...