題目連結: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;
}
轉載于:https://www.cnblogs.com/doubest/p/10189280.html