题目链接：https://codeforces.com/contest/978/problem/F
题目大意：
n个程序员,k对仇家，每个程序员有一个能力值，当甲程序员的能力值绝对大于乙程序员的能力值时，甲可以做乙的爸爸，对于每个程序员，它可以做多少人的爸爸？（仇家之间不能做父子）
题解：
第一次：WA 失误
第二次：TL 找有效徒弟和仇家时，太复杂
第三次：ML 找有效徒弟依然复杂，找仇家简单了，但是内存超了
第四次：TL 解决了内存问题，找有效徒弟复杂，找仇家简单，时间超了(最接近成功的一次)
#include<cstdio> #include<cstring> #include<algorithm> #include<map> #include<iostream> #include<vector> #include<string> #include<cmath> #include<set> using namespace std; typedef long long ll; typedef unsigned long long ull; const int N = 2e5+1; struct programmer{ int b; int r; bool operator == (const int & i){ return (this->r == i); } }inip[N],p[N]; int ans[N]; int cmp(programmer&a,programmer&b){ return a.r < b.r; } struct ene{ int eff_enemy_num = 0; }d[N]; int main(void){ int n,k; int tmp_r; scanf("%d%d",&n,&k); for(int i = 1;i<=n;i++){ scanf("%d",&tmp_r); p[i].b = i; p[i].r = tmp_r; inip[i].b = i; inip[i].r = tmp_r; } sort(p+1,p+n+1,cmp); int q1,q2; for(int i=0;i<k;i++){ scanf("%d%d",&q1,&q2); if(inip[q1].r < inip[q2].r){ d[q2].eff_enemy_num++; } else if(inip[q1].r > inip[q2].r){ d[q1].eff_enemy_num++; } } for(int i=2;i<=n;i++){ int possibel_enemy_num; int sum; possibel_enemy_num = find(p+1,p+i+1,p[i].r) - p -1; sum = possibel_enemy_num - d[p[i].b].eff_enemy_num; ans[p[i].b] = sum; } ans[p[1].b] = 0; for(int i = 1;i<=n;i++){ printf("%d",ans[i]); if(i != n){ printf(" "); } } return 0; }
第五次：TL 自认为优化，但是找有效徒弟还是太复杂
第六次：AC
代码如下：
#include<cstdio> #include<cstring> #include<algorithm> #include<map> #include<iostream> #include<vector> #include<string> #include<cmath> #include<set> using namespace std; typedef long long ll; typedef unsigned long long ull; const int N = 2e5+1; struct programmer{ int b; int r; }inip[N],p[N]; map<int,int> z; int ans[N]; int t[N]; int cmp(programmer&a,programmer&b){ return a.r < b.r; } struct ene{ int eff_enemy_num = 0; }d[N]; int main(void){ int n,k; int tmp_r; memset(t,0,sizeof(t)); scanf("%d%d",&n,&k); for(int i = 1;i<=n;i++){ scanf("%d",&tmp_r); p[i].b = i; p[i].r = tmp_r; inip[i].b = i; inip[i].r = tmp_r; } sort(p+1,p+n+1,cmp); int q1,q2; for(int i=0;i<k;i++){ scanf("%d%d",&q1,&q2); if(inip[q1].r < inip[q2].r){ d[q2].eff_enemy_num++; } else if(inip[q1].r > inip[q2].r){ d[q1].eff_enemy_num++; } } for(int i = 1;i<=n;i++){ z[p[i].r] = 0; } for(int i =1;i<=n;i++){ t[p[i].b] = z[p[i].r]; z[p[i].r]++; } for(int i=2;i<=n;i++){ int possibel_enemy_num; int sum; possibel_enemy_num = i-1-t[p[i].b]; sum = possibel_enemy_num - d[p[i].b].eff_enemy_num; ans[p[i].b] = sum; } ans[p[1].b] = 0; for(int i = 1;i<=n;i++){ printf("%d",ans[i]); if(i != n){ printf(" "); } } return 0; }
神犇代码(思路一致，但是简洁太多了):
#include <bits/stdc++.h> using namespace std; const int maxn = 2e5 + 1010; typedef long long ll; struct NODE { int va,ans; }node[maxn]; int n,k,num[maxn]; void init() { scanf("%d%d",&n,&k); for(int i=1;i<=n;i++) { scanf("%d",&node[i].va); num[i] = node[i].va; } sort(num+1,num+1+n); for(int i=1;i<=n;i++) { NODE k = node[i]; node[i].ans = lower_bound(num+1,num+1+n,k.va) - num - 1; } } int main() { init(); while(k--) { int a,b; scanf("%d%d",&a,&b); if(node[a].va < node[b].va) { node[b].ans--; } else if(node[b].va < node[a].va) { node[a].ans--; } } for(int i=1;i<=n;i++) printf("%d ",node[i].ans); return 0; }