第二题 我的程序为什么能过啊?
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5;
int n;
int nw[N + 5];
int ans[N + 5];
struct node {
int k;
int a,b,c;
}v[N + 5];
bool cmp1(node x,node y) {
return x.a > y.a;
}
bool cmp2(node x,node y) {
return x.b > y.b;
}
bool cmp3(node x,node y) {
return x.c > y.c;
}
signed main() {
cin >> n;
memset(ans,0x3f3f3f,sizeof(ans));
for(int i = 1 ; i <= n ; i ++) {
cin >> v[i].a >> v[i].b >> v[i].c;
v[i].k = i;
}
sort(v + 1,v + n + 1,cmp1);
for(int i = 1 ; i <= n ; i ++) {
int p = v[i].k;
if(v[i].a == v[i - 1].a) {
nw[p] = nw[v[i - 1].k];
} else nw[p] = i;
ans[p] = min(ans[p],nw[p]);
}
sort(v + 1,v + n + 1,cmp2);
for(int i = 1 ; i <= n ; i ++) {
int p = v[i].k;
if(v[i].b == v[i - 1].b) {
nw[p] = nw[v[i - 1].k];
} else nw[p] = i;
ans[p] = min(ans[p],nw[p]);
}
sort(v + 1,v + n + 1,cmp3);
for(int i = 1 ; i <= n ; i ++) {
int p = v[i].k;
if(v[i].c == v[i - 1].c) {
nw[p] = nw[v[i - 1].k];
} else nw[p] = i;
ans[p] = min(ans[p],nw[p]);
}
for(int i = 1 ; i <= n ; i ++)
cout << ans[i] << endl;
return 0;
}
难道我时间复杂度算错了?