这是我的一份 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;
}
需要更多的解释可以 @ 我