CF刷题-Codeforces Round #481-F. Mentors-白红宇

CF刷题-Codeforces Round #481-F. Mentors

阅读量：7119 次

发布时间：2019-06-28

本文共 3205 字，大约阅读时间需要 10 分钟。

题目链接：https://codeforces.com/contest/978/problem/F

题目大意：

n个程序员,k对仇家，每个程序员有一个能力值，当甲程序员的能力值绝对大于乙程序员的能力值时，甲可以做乙的爸爸，对于每个程序员，它可以做多少人的爸爸？（仇家之间不能做父子）

题解：

第一次：WA 失误

第二次：TL 找有效徒弟和仇家时，太复杂

第三次：ML 找有效徒弟依然复杂，找仇家简单了，但是内存超了

第四次：TL 解决了内存问题，找有效徒弟复杂，找仇家简单，时间超了(最接近成功的一次)

#include
     
      #include
      
       #include
       
        #include
        #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              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
              
                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
     
      #include
      
       #include
       
        #include
        #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              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
              
                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
               
                 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 
     
      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

你可能感兴趣的文章

【沫沫金】安卓手机版 - 日期控件

查看>>

在Linux使用exec执行命令时报的哪些错

查看>>

Waud.js – 使用HTML5降级处理的Web音频库

查看>>

WIN10 64位 JDK的安装

查看>>

CentOS 6.2目录服务之LDAP（一）

查看>>