求问
查看原帖
求问
1426031
Yezi_damn楼主2024/10/19 08:04

这是我的一份 code ,思路非常简单就是对 a、b、c 三个数组排序,之后看其择优选择排名最高的一组排名;

理论上,排一次序为 O(logn) (也有可能我记错了),顺序统计排名一次 O(n) 不会超时呀?

但是事实证明只有第一个数据点 AC 其它全 WA ,求佬调教!

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAX=2764955231;
struct node{
	int a,b,c;
}bs[200010];
int ba[200010],cnt=1,kk=1;
bool cmpa(node a,node b){return a.a>b.a;}
bool cmpb(node a,node b){return a.b>b.b;}
bool cmpc(node a,node b){return a.c>b.c;}
signed main()
{
	memset(ba,MAX,sizeof(ba));
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>bs[i].a>>bs[i].b>>bs[i].c;
//		bs[i]=i;
	}
	sort(bs+1,bs+n+1,cmpa);
	for(int i=1;i<=n;i++)
	{
//		cout<<bs[i].a<<endl;
		if(bs[i].a>bs[i+1].a) ba[i]=min(ba[i],cnt),cnt+=kk,kk=1;
		else ba[i]=min(ba[i],cnt),kk++;
	}
	cnt=1,kk=1;
	sort(bs+1,bs+n+1,cmpb);
	for(int i=1;i<=n;i++)
	{
//		cout<<bs[i].a<<endl;
//		cout<<cnt<<endl;
		if(bs[i].b>bs[i+1].b) ba[i]=min(ba[i],cnt),cnt+=kk,kk=1;
		else ba[i]=min(ba[i],cnt),kk++;
	}
	cnt=1,kk=1;
	sort(bs+1,bs+n+1,cmpc);
//	for(int i=1;i<=n;i++) cout<<bs[i].c<<endl;
	for(int i=1;i<=n;i++)
	{
//		cout<<bs[i].a<<endl;
		if(bs[i].c>bs[i+1].c) ba[i]=min(ba[i],cnt),cnt+=kk,kk=1;
		else ba[i]=min(ba[i],cnt),kk++;
	}
	for(int i=1;i<=n;i++) cout<<ba[i]<<endl;
}

需要更多的解释可以 @ 我

2024/10/19 08:04
加载中...