题解

41 条题解

  • 3
    @ 2017-11-06 16:12:13

    VIJOS数据比较水,用sort卡一个点,stable_sort就全过,然而在洛谷上会被卡,正解应该是归并排序
    可以知道,每一轮比赛后都会有胜者组和败者组,每一组的要么都加1,要么都不变,因此胜者组和败者组仍各自是有序的,这样我们就可以O(n)的进行归并排序
    贴代码

    #include<iostream>
    #include<cstdio>
    #include<algorithm>
    using namespace std;
    
    struct node
    {
        int num,s,w;
    }q[200010];
    
    struct node1
    {
        int num,s,w;
    }win[100010];
    
    struct node2
    {
        int num,s,w;    
    }lose[100010];
    int cmp(const node&x,const node&y)
    {
        if(x.s>y.s)
         return 1;
        if(x.s<y.s)
         return 0;
        return x.num<y.num;
    }
    int main()
    {
        int n,r,p,i,len1,len2;
        scanf("%d%d%d",&n,&r,&p);
        for(i=1;i<=2*n;i++)
         scanf("%d",&q[i].s);
        for(i=1;i<=2*n;i++)
        {
            q[i].num=i;
            scanf("%d",&q[i].w);
        }
        sort(q+1,q+2*n+1,cmp);
        while(r)
        {
            for(i=1;i<=n;i++)
             if(q[2*i].w>q[2*i-1].w)
              {
               q[2*i].s++;
               win[i].num=q[2*i].num;
               win[i].s=q[2*i].s;
               win[i].w=q[2*i].w;
               lose[i].num=q[2*i-1].num;
               lose[i].s=q[2*i-1].s;
               lose[i].w=q[2*i-1].w;
              }
              else
              {
               q[2*i-1].s++;
               win[i].num=q[2*i-1].num;
               win[i].s=q[2*i-1].s;
               win[i].w=q[2*i-1].w;
               lose[i].num=q[2*i].num;
               lose[i].s=q[2*i].s;
               lose[i].w=q[2*i].w;
              }
            len1=1;
            len2=1;
            while(len1<=n&&len2<=n)
            {
                if(win[len1].s>lose[len2].s)
                 {
                  q[len1+len2-1].num=win[len1].num;
                  q[len1+len2-1].s=win[len1].s;
                  q[len1+len2-1].w=win[len1].w;
                  len1++;
                 }
                 if(win[len1].s<lose[len2].s)
                 {
                  q[len1+len2-1].num=lose[len2].num;
                  q[len1+len2-1].s=lose[len2].s;
                  q[len1+len2-1].w=lose[len2].w;
                  len2++;
                 }
                 if(win[len1].s==lose[len2].s)
                   if(win[len1].num<lose[len2].num)
                    {
                    q[len1+len2-1].num=win[len1].num;
                    q[len1+len2-1].s=win[len1].s;
                    q[len1+len2-1].w=win[len1].w;
                    len1++;
                    }
                    else
                    {
                    q[len1+len2-1].num=lose[len2].num;
                    q[len1+len2-1].s=lose[len2].s;
                    q[len1+len2-1].w=lose[len2].w;
                    len2++;
                    }
            }
            while(len1<=n)
            {
                q[len1+len2-1].num=win[len1].num;
                q[len1+len2-1].s=win[len1].s;
                q[len1+len2-1].w=win[len1].w;
                len1++;
            }
            while(len2<=n)
            {
                q[len1+len2-1].num=lose[len2].num;
                q[len1+len2-1].s=lose[len2].s;
                q[len1+len2-1].w=lose[len2].w;
                len2++;
            }
            r--;
        }
        printf("%d",q[p].num);
        return 0;
    }
    
    • @ 2018-03-24 11:33:35

      受到dalao的启发才想到用归并排序,不过我写的比你简单一点。其实建一个结构体就行了,也不用一项项的赋值,一条等式就搞定了,还有ELSE语句的运用...不过我的程序比你的慢一点

      状态 耗时 内存占用

      #1 Accepted 2ms 2.363 MiB
      #2 Accepted 4ms 2.34 MiB
      #3 Accepted 4ms 2.375 MiB
      #4 Accepted 18ms 2.488 MiB
      #5 Accepted 37ms 4.5 MiB
      #6 Accepted 48ms 2.73 MiB
      #7 Accepted 85ms 3.375 MiB
      #8 Accepted 167ms 4.965 MiB
      #9 Accepted 180ms 5.0 MiB
      #10 Accepted 184ms 4.969 MiB

      #include<bits/stdc++.h>
      using namespace std;
      struct player
      {
          int s,w,num;
      }a[200005],win[100005],lose[100005];
      bool cmp(const player &x,const player &y)
      {
          if (x.s==y.s)
              return x.num<y.num;
          return x.s>y.s;
      }   
      int main()
      {
          int n,r,q;
          int i,w,l;
          int lenw,lenl;
          cin>>n>>r>>q;
          n=n*2;
          for (i=1;i<=n;i++)
              cin>>a[i].s;
          for (i=1;i<=n;i++)
              cin>>a[i].w;
          for (i=1;i<=n;i++)
              a[i].num=i;
          sort(a+1,a+n+1,cmp);
          while (r>0)
          {
              lenw=0;
              lenl=0;
              for (i=1;i<=n;i=i+2)
              {
                  if(a[i].w>a[i+1].w)
                  {   
                      a[i].s++;
                      win[++lenw]=a[i];
                      lose[++lenl]=a[i+1];
                  }
                  else
                  {   
                      a[i+1].s++;
                      win[++lenw]=a[i+1];
                      lose[++lenl]=a[i];
                  }
              }
              w=1;
              l=1;
              i=1;
              while (w<=lenw&&l<=lenl)
              {
                  if ((win[w].s>lose[l].s)||(win[w].s==lose[l].s&&win[w].num<lose[l].num))
                  {   
                      a[i]=win[w];
                      w++;
                  }
                  else
                  {
                      a[i]=lose[l];
                      l++;
                  }
                  i++;    
              }
              while (w<=lenw)
              {
                  a[i]=win[w];
                  w++;
                  i++;
              }
              while (l<=lenl)
              {
                  a[i]=lose[l];
                  l++;
                  i++;
              }
              r--;
          }
          cout<<a[q].num;
          return 0;
      }
      
      
  • 2
    @ 2017-07-04 13:48:08

    嘛,模拟加排序,为什么难度是7呢2333,虽然犯了好几个脑残错误导致WA了好几次(sort貌似不会超时吧。。。我试了一下sort最后一个点800ms

    #include<iostream>
    #include<algorithm>
    using namespace std;
    typedef struct Member{
        int ability;
        int score;
        int num;
    }Member;
    Member member[200050];
    bool cmp(const Member& a,const Member& b){
        if (a.score==b.score) return a.num<b.num;
        else return a.score>b.score;
    }
    void Rank(int n){
        stable_sort(member,member+2*n,cmp);
    }
    void compare(int a,int b){
        if(member[a].ability>member[b].ability){
            member[a].score++;
        }
        else{
            member[b].score++;
        }
        return;
    }
    int main(void){
        int n,r,q;
        scanf("%d%d%d",&n,&r,&q);
        for(int i=0;i<2*n;i++){
            scanf("%d",&member[i].score);
            member[i].num=i;
        }
        for(int i=0;i<2*n;i++){
            scanf("%d",&member[i].ability);
        }
        Rank(n);
        for(int i=0;i<r;i++){
            for(int j=0;j<2*n;j+=2){
                compare(j,j+1);
            }
            Rank(n);
        }
        cout<<member[q-1].num+1<<endl;
    } 
    
  • 2
    @ 2017-05-27 22:17:48
    //p1771
    #include<iostream>
    #include<vector>
    #include<algorithm>
    using namespace std;
    
    struct player
    {
        int num,score,quality;
    };
    
    int n,r,q;
    vector<player> a;
    
    bool cmp(const player& a,const player& b)
    {
        if (a.score==b.score) return a.num<b.num;
        return a.score>b.score;
    }
    
    void round()
    {
        for (int i=0;i<2*n;i+=2)
            if (a[i].quality>a[i+1].quality) a[i].score++;
            else a[i+1].score++;
        sort(a.begin(),a.end(),cmp);
    }
    
    int main()
    {
        int i,t;
        player temp;
        cin>>n>>r>>q;
        for (i=0;i<2*n;i++)
        {
            cin>>t;
            temp.num=i;
            temp.score=t;
            a.push_back(temp);
        }
        for (i=0;i<2*n;i++)
        {
            cin>>t;
            a[i].quality=t;
        }
        sort(a.begin(),a.end(),cmp);
        for (i=0;i<r;i++) round();
        cout<<a[q-1].num+1<<endl;
        return 0;
    }
    
    
  • 1
    @ 2021-08-21 12:17:57
    #include<bits/stdc++.h>
    using namespace std;
    
    
    int n,k,q,s;
    struct st{
        int num; 
        int grade;
        int shili;
    };
    
    st a[210000],b[105000],c[105000]; 
    int read()
    {
        int x=0;
        char s=getchar();
        while(s>'9' || s<'0')
            s=getchar();
        while(s<='9' && s>='0')
            x=x*10+s-'0',s=getchar();
        return x;
    }
    
    bool cmp(st a1,st a2)
    {
        if(a1.grade!=a2.grade)
            return a1.grade>a2.grade;
        else
            return a1.num<a2.num;
    }
    
    void work() 
    {
        int lb=0,lc=0,la;
        for(int i=1; i<n*2; i+=2){
            if(a[i].shili>a[i+1].shili){
                a[i].grade++;
                b[++lb]=a[i];
                c[++lc]=a[i+1];
            }
            else{
                a[i+1].grade++;
                b[++lb]=a[i+1];
                c[++lc]=a[i];
            }
        }
        lb=1,lc=1,la=1;
        while(lb<=n && lc<=n){
            if(cmp(b[lb],c[lc]))
                a[la++]=b[lb++];
            else
                a[la++]=c[lc++];
        }
        while(lb<=n)
            a[la++]=b[lb++]; 
        while(lc<=n)
            a[la++]=c[lc++];
    }
    
    int main()
    {
        n=read(),k=read(),q=read();
        for(int i=1; i<=n*2; i++){
            a[i].num=i;
            a[i].grade=read();
        }
        for(int i=1; i<=n*2; i++)
            a[i].shili=read();
        sort(a+1,a+n*2+1,cmp);
        for(int i=1; i<=k; i++)
            work();
        cout<<a[q].num;
        return 0;
    }
    
  • 1
    @ 2019-02-12 17:28:13

    归并排序,速度更快

    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<cmath>
    #include<iostream>
    using namespace std;
    struct person{
        int score;
        int num;
        int ability;
        person& operator = (const person&p){
            score = p.score;
            num = p.num;
            ability = p.ability;
            return *this;
        }
        bool operator < (const person&p){   //小于表示排在前面,下同
            if(score>p.score) return true;
            else if(score==p.score&&num<p.num) return true;
            return false;
        }
    } p[200005],win[100005],lose[100005];
    int n,r,q;
    int main(){
        scanf("%d%d%d",&n,&r,&q);
        for(int i=0;i<2*n;i++){
            scanf("%d",&p[i].score);
            p[i].num = i+1;
        }
        for(int i=0;i<2*n;i++){  //输入实力值
            scanf("%d",&p[i].ability);
        }
        sort(p,p+2*n);
        for(int i=0;i<r;i++){
            for(int j=0;j<n;j++){
                if(p[2*j].ability > p[2*j+1].ability){
                    p[2*j].score++;
                    win[j] = p[2*j];
                    lose[j] = p[2*j+1];
                }else{
                    p[2*j+1].score++;
                    win[j] = p[2*j+1];
                    lose[j] = p[2*j];
                }
            }
            int wj=0,lj=0;
            while(wj<n&&lj<n){
                if(win[wj]<lose[lj]) p[wj+lj]=win[wj],wj++;
                else p[wj+lj]=lose[lj],lj++;
            }
            if(wj==n) for(;lj<n;lj++) p[wj+lj]=lose[lj];
            else for(;wj<n;wj++) p[wj+lj]=win[wj];
        }
        cout<<p[q-1].num;
        return 0;
    }
    
    
  • 1
    @ 2019-02-12 16:07:55

    普通的sort,一开始还用了优先队列,结果发现贼慢,直接用数组就险AC了。

    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<cmath>
    #include<iostream>
    #include<vector>
    #include<queue>
    #include<map>
    using namespace std;
    
    bool cmp(pair<int,int> a,pair<int,int> b){
        if(a.first>b.first) return true;
        else if(a.first==b.first&&a.second<b.second) return true;
        return false;
    }
    int n,r,q,cap[200005];
    pair<int,int> p[200005],a,b;
    int main(){
        scanf("%d%d%d",&n,&r,&q);
        for(int i=0;i<2*n;i++){
            scanf("%d",&p[i].first);
            p[i].second = i+1;
        }
        sort(p,p+2*n,cmp);
        for(int i=1;i<=2*n;i++){  //输入实力值
            scanf("%d",cap+i);
        }
        for(int i=0;i<r;i++){
            for(int j=0;j<n;j++){
                p[2*j].first += (cap[p[2*j].second]>cap[p[2*j+1].second]) ;
                p[2*j+1].first += (cap[p[2*j].second]<cap[p[2*j+1].second]);
            }
            sort(p,p+2*n,cmp);
        }
        cout<<p[q-1].second;
        return 0;
    }
    
    
  • 1
    @ 2018-11-04 23:02:25

    #include<iostream>
    #include<algorithm>
    using namespace std;
    struct matcher{
    int ID,score,power;
    matcher(int i,int s,int p)
    {
    ID=i;
    score=s;
    power=p;
    }
    matcher()
    {
    matcher(0,0,0);
    }
    };
    struct cmp{
    bool operator() (matcher a,matcher b)
    {
    if(a.score==b.score) return a.ID<b.ID;
    else return a.score>b.score;
    }
    };
    int n,r,q;
    matcher mats[200001];
    int main()
    {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>r>>q;
    for(int i=1;i<=2*n;i++)
    {
    cin>>mats[i].score;
    mats[i].ID=i;
    }

    for(int i=1;i<=2*n;i++)
    {
    cin>>mats[i].power;
    }

    stable_sort(mats+1,mats+2*n+1,cmp());
    for(int i=0;i<r;i++)
    {
    for(int j=0;j<=2*n;j+=2)
    {
    if(mats[j].power >= mats[j-1].power) mats[j].score++;
    else mats[j-1].score++;
    }
    stable_sort(mats+1,mats+2*n+1,cmp());
    }
    cout<<mats[q].ID;
    return 0;
    }

  • 1
    @ 2018-04-08 00:45:36

    #1 Accepted 7ms 256.0 KiB
    #2 Accepted 1ms 256.0 KiB
    #3 Accepted 1ms 256.0 KiB
    #4 Accepted 26ms 384.0 KiB
    #5 Accepted 61ms 764.0 KiB
    #6 Accepted 174ms 1.25 MiB
    #7 Accepted 395ms 2.469 MiB
    #8 Accepted 551ms 4.855 MiB
    #9 Accepted 776ms 4.375 MiB
    #10 Accepted 998ms 4.75 MiB
    这个。。。算巧合吗

  • 1
    @ 2017-12-02 15:18:54

    #include<bits/stdc++.h>
    using namespace std;
    int N,n,R,Q,win[100001],lose[100001],wini,losei,ki;
    struct node
    {
    int s,w,num;
    }f[200001],k[200001];
    bool cmp(node a,node b)
    {
    return a.s>b.s ||(a.s==b.s && a.num<b.num);
    }
    int gi()
    {
    int x=0;char ch=getchar();
    while(ch<'0' || ch>'9')ch=getchar();
    while(ch>='0' && ch<='9')x=x*10+ch-48,ch=getchar();
    return x;
    }
    int main()
    {
    N=gi();n=N*2;R=gi();Q=gi();
    for(int t=1;t<=n;t++)
    {
    f[t].s=gi();
    f[t].num=t;
    }
    for(int t=1;t<=n;t++)
    {
    f[t].w=gi();
    }
    sort(f+1,f+n+1,cmp);
    while(R--)
    {
    wini=losei=1;
    for(int tt=1;tt<=n;tt+=2)
    {
    if(f[tt].w>f[tt+1].w)f[tt].s+=1,win[wini++]=tt,lose[losei++]=tt+1;
    else f[tt+1].s+=1,win[wini++]=tt+1,lose[losei++]=tt;
    }
    wini=losei=ki=1;
    while(wini<=N && losei<=N)
    {
    if((f[win[wini]].s>f[lose[losei]].s) || (f[win[wini]].s==f[lose[losei]].s && f[win[wini]].num<f[lose[losei]].num))
    k[ki++]=f[win[wini++]];
    else k[ki++]=f[lose[losei++]];
    }
    while(wini<=N)
    k[ki++]=f[win[wini++]];
    while(losei<=N)
    k[ki++]=f[lose[losei++]];
    for(int ii=1;ii<=n;ii++)
    f[ii]=k[ii];
    }
    printf("%d",f[Q].num);
    return 0;
    }

  • 1
    @ 2017-05-11 13:28:08

    其实,c++ 的 stl 中的 sort() 并不是不可以 (可能是 O2). 注意 n 要乘以 2, 以及排序和开数组.
    c++ AC:

    #include <iostream>
    #include <algorithm>
    using namespace std;
    
    const int maxn = 200010;
    int w[maxn];
    struct player {
        int id, s;
        bool operator < (const player &other) const {    // 很重要!
            return s > other.s || (s == other.s && id < other.id);
        }
    } a[maxn];
    
    int main() {
        ios::sync_with_stdio(false);    // 很重要!
        int n, r, q;
        cin >> n >> r >> q;
        n *= 2;                         // 很重要!
        for (int i = 0; i < n; i++) {
            a[i].id = i;
            cin >> a[i].s;
        }
        for (int i = 0; i < n; i++)
            cin >> w[i];
        sort(a, a + n);
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < n; j += 2)
                a[j + (w[a[j].id] < w[a[j+1].id])].s++;
            sort(a, a + n);
        }
        cout << a[q - 1].id + 1 << endl;
        return 0;
    }
    
  • 1
    @ 2016-12-06 03:08:13
    #include <iostream>
    #include <stdlib.h>
    #include <stdio.h> 
    #include <algorithm>  
    using namespace std;
    
    struct anode
    {
      int fenshu;
      int shili;
      int bianhao;
    };
    
    bool cmp(const anode &x, const anode &y)
    {
      if(x.fenshu!=y.fenshu){return x.fenshu>y.fenshu;}
      else{return x.bianhao<y.bianhao;}
    }
    
    int main()
    {
      int n,r,q;
      cin>>n>>r>>q;
    
      anode a[200050];  
      for(int i=1;i<=2*n;i++)
      {
        scanf("%d",&a[i].fenshu);
        a[i].bianhao=i;
      }  
      for(int i=1;i<=2*n;i++){scanf("%d",&a[i].shili);}
    
    //__________________________________________________
    
      for(int j=1;j<=r;j++)
      {
        stable_sort(a+1,a+1+2*n,cmp);
        for(int i=1;i<=2*n-1;i=i+2)
        {
          if(a[i].shili<a[i+1].shili){a[i+1].fenshu++;}
          else{a[i].fenshu++;}
        }
      }
      stable_sort(a+1,a+1+2*n,cmp);
    //___________________________________________________
    
      printf("%d",a[q].bianhao);
    
      return 0;
    }
    使用cincout 或者sort()都会挂2个点
    应该用scanfprintf  和 stable_sort()
    
  • 0
    @ 2018-11-04 23:02:36

    #include<iostream>
    #include<algorithm>
    using namespace std;
    struct matcher{
    int ID,score,power;
    matcher(int i,int s,int p)
    {
    ID=i;
    score=s;
    power=p;
    }
    matcher()
    {
    matcher(0,0,0);
    }
    };
    struct cmp{
    bool operator() (matcher a,matcher b)
    {
    if(a.score==b.score) return a.ID<b.ID;
    else return a.score>b.score;
    }
    };
    int n,r,q;
    matcher mats[200001];
    int main()
    {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>r>>q;
    for(int i=1;i<=2*n;i++)
    {
    cin>>mats[i].score;
    mats[i].ID=i;
    }

    for(int i=1;i<=2*n;i++)
    {
    cin>>mats[i].power;
    }

    stable_sort(mats+1,mats+2*n+1,cmp());
    for(int i=0;i<r;i++)
    {
    for(int j=0;j<=2*n;j+=2)
    {
    if(mats[j].power >= mats[j-1].power) mats[j].score++;
    else mats[j-1].score++;
    }
    stable_sort(mats+1,mats+2*n+1,cmp());
    }
    cout<<mats[q].ID;
    return 0;
    }

  • 0
    @ 2017-11-28 14:17:39
    #include<cstdio>
    #include<algorithm>
    struct player{
        int num;
        int grade;
        int strength;
    };
    int n, round, need;
    player a[200010], b[200010], ans[200010];
    bool cmp(const player& a, const player& b){
        if(a.grade==b.grade) return a.num<b.num;
        else return a.grade>b.grade;
    }
    void solve(){
        int _a=1, _b=1;
        for(int i=1; i<=n*2; i+=2){
            if(ans[i].strength>ans[i+1].strength){
                ans[i].grade++;
                a[_a++]=ans[i];
                b[_b++]=ans[i+1];
            }
            else{
                ans[i+1].grade++;
                a[_a++]=ans[i+1];
                b[_b++]=ans[i];
            }
        }
        int i=1, j=1, k=1;
        while(i<_a&&j<_b){
            if(cmp(a[i], b[j])){
                ans[k++]=a[i++];
            }
            else ans[k++]=b[j++];
        }
        while(i<_a) ans[k++]=a[i++];
        while(j<_b) ans[k++]=b[j++];
    }
    int main(){
        scanf("%d%d%d", &n, &round, &need);
        for(int i=1; i<=n*2; i++){
            scanf("%d", &ans[i].grade);
            ans[i].num=i;
        }
        for(int i=1; i<=n*2; i++){
            scanf("%d", &ans[i].strength);
        }
        std::sort(ans+1, ans+2*n+1, cmp);
        for(int i=1; i<=round; i++) solve();
        printf("%d", ans[need].num);
        return 0;
    }
                        
    
  • 0
    @ 2017-10-07 14:52:28

    嗯,挺简单的,其实不难

    
    Var
            n,r,q,i,cc,rs,k:longint;
            fs,sl,b:array[1..300000]of longint;
            sz,lz,szfs,lzfs,szsl,lzsl:array[1..300000]of longint;
    
    Procedure quicksort(l,r:longint);
    Var
            i,j,mid,t,bh:longint;
    Begin
            i:=l; j:=r; mid:=fs[(i+j) div 2]; bh:=b[(i+j) div 2];
            repeat
                    while (fs[i]>mid) or ((fs[i]=mid) and (b[i]<bh)) do inc(i);
                    while (fs[j]<mid) or ((fs[j]=mid) and (b[j]>bh)) do dec(j);
                    if i<=j then
                    begin
                            t:=fs[i]; fs[i]:=fs[j]; fs[j]:=t;
                            t:=sl[i]; sl[i]:=sl[j]; sl[j]:=t;
                            t:=b[i]; b[i]:=b[j]; b[j]:=t;
                            inc(i); dec(j);
                    end;
            until i>=j;
            if i<r then quicksort(i,r);
            if l<j then quicksort(l,j);
    End;
    
    Procedure hb;
    Var
            rs,lose,win,i:longint;
    Begin
            fillchar(b,sizeof(b),0);
            fillchar(fs,sizeof(fs),0);
            fillchar(sl,sizeof(sl),0);
            win:=1; lose:=1; rs:=0;
            while (win<=n) and (lose<=n) do
            begin
                    inc(rs);
                    if (szfs[win]>lzfs[lose]) or ((szfs[win]=lzfs[lose]) and (sz[win]<lz[lose])) then
                    begin
                            sl[rs]:=szsl[win];
                            fs[rs]:=szfs[win];
                            b[rs]:=sz[win];
                            inc(win);
                    end
                    else
                    if (szfs[win]<lzfs[lose]) or ((szfs[win]=lzfs[lose]) and (sz[win]>lz[lose])) then
                    begin
                            sl[rs]:=lzsl[lose];
                            fs[rs]:=lzfs[lose];
                            b[rs]:=lz[lose];
                            inc(lose);
                    end;
            end;
    
            if win<=n then
            begin
                    rs:=win;
                    for i:=n*2-(n-win+1)+1 to n*2 do
                    begin
                            sl[i]:=szsl[rs];
                            fs[i]:=szfs[rs];
                            b[i]:=sz[rs];
                            inc(rs);
                    end;
            end;
    
            if lose<=n then
            begin
                    rs:=lose;
                    for i:=2*n-(n-lose+1)+1 to 2*n do
                    begin
                            sl[i]:=lzsl[rs];
                            fs[i]:=lzfs[rs];
                            b[i]:=lz[rs];
                            inc(rs);
                    end;
            end;
    End;
    
    Begin
    //assign(input,'1.in');reset(input);
            readln(n,r,q);
            for i:=1 to n*2 do
                    read(fs[i]);
            for i:=1 to n*2 do
                    read(sl[i]);
            for i:=1 to n*2 do
                    b[i]:=i;
            quicksort(1,n*2);
            cc:=0;
            while cc<r do
            begin
                    inc(cc);
                    k:=1;
                    rs:=0;
                    while k<=n*2 do
                    begin
                            if sl[k]>sl[k+1] then
                            begin
                                    inc(rs);
                                    sz[rs]:=b[k];
                                    szfs[rs]:=fs[k]+1;
                                    szsl[rs]:=sl[k];
                                    lz[rs]:=b[k+1];
                                    lzfs[rs]:=fs[k+1];
                                    lzsl[rs]:=sl[k+1];
                            end
                            else
                            begin
                                    inc(rs);
                                    sz[rs]:=b[k+1];
                                    szfs[rs]:=fs[k+1]+1;
                                    szsl[rs]:=sl[k+1];
                                    lz[rs]:=b[k];
                                    lzfs[rs]:=fs[k];
                                    lzsl[rs]:=sl[k];
                            end;
                            inc(k,2);
                    end;
                    hb;
            end;
            writeln(b[q]);
            readln;
    End.
    
    
  • 0
    @ 2017-09-17 18:09:06

    可以的,很完美的题目
    sort最后一个点完美TLE,看大神题解说用stable_sort就能过
    然后
    就真的过了
    最后一个点跑了600MS

    #include<iostream>
    #include<cstdio>
    #include<algorithm>
    using namespace std;
    
    struct player{
        int num,goal,li;
    }q[200010];
    
    int comp(const player&x,const player&y)
    {
        if(x.goal>y.goal)
         return 1;
        else
         if(x.goal<y.goal)
          return 0;
           else
          if(x.num>y.num)
           return 0;
            else 
           return 1;
    }
    
    int main()
    {
        int n,r,m,i;
        cin>>n>>r>>m;
        for(i=1;i<=2*n;i++)
         scanf("%d",&q[i].goal);
        for(i=1;i<=2*n;i++)
        {
            scanf("%d",&q[i].li);
            q[i].num=i;
        }
        sort(q+1,q+2*n+1,comp);
        while(r--)
        {
            stable_sort(q+1,q+2*n+1,comp);
            for(i=1;i<=n;i++)
            {
                if(q[2*i].li>q[2*i-1].li)
                 q[2*i].goal++;
                 else
                 q[2*i-1].goal++;
            }
        }
        sort(q+1,q+2*n+1,comp);
        cout<<q[m].num;
        return 0;
    }
    
  • 0
    @ 2017-07-28 17:09:19

    归并排序
    #include<iostream>
    #include<cstdlib>
    #include<cstdio>
    #include <algorithm>
    using namespace std;
    int i,j,r,x,y,N,R,Q,temp1=0,temp2=0;
    struct apple{
    int no,score,w;
    bool operator<(const apple &other)const{
    return score>other.score || (score==other.score && no<other.no);
    }
    }s[300000],a1[200000],a2[200000];
    int main(){
    scanf("%d%d%d",&N,&R,&Q);
    for(i=1;i<=2*N;i++){
    s[i].no=i;
    scanf("%d",&s[i].score);
    }

    for(i=1;i<=2*N;i++)
    scanf("%d",&s[i].w );

    sort(s+1,s+2*N+1);

    for(i=1;i<=R;i++){
    temp1=0;temp2=0;

    for(j=1;j<=N;j++){
    int xx=j*2-1;
    if(s[xx].w > s[xx+1].w ){
    s[xx].score++;
    a1[++temp1]=s[xx];
    a2[++temp2]=s[xx+1];
    }
    else {
    s[xx+1].score++;
    a1[++temp1]=s[xx+1];
    a2[++temp2]=s[xx];
    }
    }

    temp1=0;
    x=1; y=1;
    while(x<=N && y<=N){
    if(a1[x].score>a2[y].score || (a1[x].score==a2[y].score && a1[x].no<a2[y].no))
    {
    s[++temp1]=a1[x];
    x++;
    }
    else {
    s[++temp1]=a2[y];
    y++;
    }
    }
    if(x<=N)
    for(r=x;r<=N;r++)s[++temp1]=a1[r];
    if(y<=N)
    for(r=y;r<=N;r++)s[++temp1]=a2[r];

    }
    printf("%d\n",s[Q].no);
    return 0;
    }

  • 0
    @ 2017-07-28 17:08:40

    #include<iostream>
    #include<cstdlib>
    #include<cstdio>
    #include <algorithm>
    using namespace std;
    int i,j,r,x,y,N,R,Q,temp1=0,temp2=0;
    struct apple{
    int no,score,w;
    bool operator<(const apple &other)const{
    return score>other.score || (score==other.score && no<other.no);
    }
    }s[300000],a1[200000],a2[200000];
    int main(){
    freopen("swiss10.in","r",stdin);
    freopen("swiss.out","w",stdout);
    scanf("%d%d%d",&N,&R,&Q);
    for(i=1;i<=2*N;i++){
    s[i].no=i;
    scanf("%d",&s[i].score);
    }

    for(i=1;i<=2*N;i++)
    scanf("%d",&s[i].w );

    sort(s+1,s+2*N+1);

    for(i=1;i<=R;i++){
    temp1=0;temp2=0;

    for(j=1;j<=N;j++){
    int xx=j*2-1;
    if(s[xx].w > s[xx+1].w ){
    s[xx].score++;
    a1[++temp1]=s[xx];
    a2[++temp2]=s[xx+1];
    }
    else {
    s[xx+1].score++;
    a1[++temp1]=s[xx+1];
    a2[++temp2]=s[xx];
    }
    }

    temp1=0;
    x=1; y=1;
    while(x<=N && y<=N){
    if(a1[x].score>a2[y].score || (a1[x].score==a2[y].score && a1[x].no<a2[y].no))
    {
    s[++temp1]=a1[x];
    x++;
    }
    else {
    s[++temp1]=a2[y];
    y++;
    }
    }
    if(x<=N)
    for(r=x;r<=N;r++)s[++temp1]=a1[r];
    if(y<=N)
    for(r=y;r<=N;r++)s[++temp1]=a2[r];

    }
    printf("%d\n",s[Q].no);
    return 0;
    }

  • 0
    @ 2017-07-05 20:36:55

    #1 Accepted 3ms 256.0KiB
    #2 Accepted 3ms 256.0KiB
    #3 Accepted 3ms 256.0KiB
    #4 Accepted 29ms 384.0KiB
    #5 Accepted 65ms 2.363MiB
    #6 Accepted 172ms 996.0KiB
    #7 Accepted 402ms 1.5MiB
    #8 Accepted 528ms 2.625MiB
    #9 Accepted 780ms 2.715MiB
    #10 Accepted 954ms 2.594MiB
    最后一点 954ms强行AC

    #include<cstdio>
    #include<iostream>
    #include<algorithm>
    #define MAXN 200010
    
    using namespace std;
    
    int n,r,q;
    
    struct node {
        int w;
        int s;
        int id;
    };
    node a[MAXN];
    
    inline void read(int&x) {
        x=0;int f=1;char c=getchar();
        while(c>'9'||c<'0') {if(c=='-') f=-1;c=getchar();}
        while(c>='0'&&c<='9') {x=(x<<1)+(x<<3)+c-48;c=getchar();}
        x=x*f;
    }
    
    inline bool cmp(const node x,const node y) {
        if(x.s==y.s) return x.id<y.id;
        else return x.s>y.s;
    } 
    
    int main() {
        read(n);read(r);read(q);
        for(int i=1;i<=n*2;i++) {
            a[i].id=i;
            read(a[i].s);
        }
        for(int i=1;i<=2*n;i++) read(a[i].w);
        sort(a+1,a+1+2*n,cmp);
        while(r--) {
            for(int i=1;i<=n*2;i+=2) {
                if(a[i].w>a[i+1].w) a[i].s++;
                else a[i+1].s++;
            }
            sort(a+1,a+1+2*n,cmp);
        }
        printf("%d\n",a[q].id);
        return 0;
    }
    
  • 0
    @ 2017-01-29 20:23:10

    类似归并排序的方法,时间复杂度O(RN)
    #include <cstdio>
    #include <cstring>
    #include <algorithm>

    using namespace std;

    #define rep(id,a,b) for(int id=(a);id<(b);++id)
    #define irep(id,a,b) for(int id=(a);id>(b);--id)
    #define reset(arr,c) memset(arr,c,sizeof(arr))

    typedef long long int64;

    const int maxN=100000+5;

    struct Player
    {
    int s,n,a;
    void assign(int _s,int _n,int _a) { s=_s,a=_a,n=_n; }
    bool operator > (const Player& other) const
    {
    return s > other.s || (s == other.s && n < other.n);
    }
    Player& operator = (const Player& other)
    {
    s=other.s,n=other.n,a=other.a;
    return *this;
    }
    };

    Player win[maxN],lose[maxN];
    Player all[maxN<<1];
    int N,R,Q;

    void input()
    {
    scanf("%d%d%d",&N,&R,&Q);
    rep(i,0,N<<1) all[i].n=i+1;
    rep(i,0,N<<1) scanf("%d",&all[i].s);
    rep(i,0,N<<1) scanf("%d",&all[i].a);
    }

    #include <functional>

    int solve()
    {
    sort(all,all+(N<<1),greater<Player>());
    while(R--)
    {
    rep(i,0,N)
    {
    int w=(all[i<<1].a > all[(i<<1)|1].a)?(i<<1):(i<<1)|1;
    win[i]=all[w],lose[i]=all[w^1];
    ++win[i].s;
    }
    int w=0,l=0;
    while(w<N && l<N)
    {
    if(win[w]>lose[l]) { all[w+l]=win[w]; ++w; }
    else { all[w+l]=lose[l]; ++l; }
    }
    if(w<N) rep(i,w,N) all[i+l]=win[i];
    else rep(i,l,N) all[i+w]=lose[i];
    }
    return all[Q-1].n;
    }

    int main() { input(); printf("%d\n",solve()); return 0; }

  • 0
    @ 2016-11-17 11:58:55

    STL大法好,不用手打归并排序,
    本题中使用sort()会TLE,应该用stable_sort()
    原因:每一轮过后,每个人的排名不会变化太大,
    sort()排序时会把元素打乱,而stable_sort()不会把元素打乱。
    时间复杂度O(r N logN)

    #include<cstdio>
    #include<algorithm>
    using namespace std;
    
    const int maxn=200020;
    int n,r,q,w[maxn];
    
    struct Node
    {
        int id,s;
        void read(int i)
        {
            id=i;
            scanf("%d",&s);
        }
        bool operator < (const Node & x) const 
        {
            return s>x.s||s==x.s&&id<x.id;
        }
    }a[maxn];
    
    int main()
    {
        scanf("%d%d%d",&n,&r,&q);
        n*=2;
        for (int i=0;i<n;i++) a[i].read(i);
        for (int i=0;i<n;i++) scanf("%d",&w[i]);
        sort(a,a+n);
        for (int i=0;i<r;i++)
        {
            for (int j=0;j<n;j+=2)
                a[j+(w[a[j].id]<w[a[j+1].id])].s++;//胜者加分 
            stable_sort(a,a+n);//归并排序,注意:此处用sort()会TLE
        }
        printf("%d\n",a[q-1].id+1);//排名从0开始 
        
        return 0;
    }
    

    使用stable_sort()
    测试数据 #6: Accepted, time = 218 ms, mem = 3692 KiB, score = 10
    测试数据 #7: Accepted, time = 328 ms, mem = 4468 KiB, score = 10
    测试数据 #8: Accepted, time = 437 ms, mem = 4468 KiB, score = 10
    测试数据 #9: Accepted, time = 515 ms, mem = 4472 KiB, score = 10
    Accepted, time = 1669 ms, mem = 4472 KiB, score = 100
    .
    .
    使用sort()
    测试数据 #6: Accepted, time = 515 ms, mem = 2856 KiB, score = 10
    测试数据 #7: Accepted, time = 734 ms, mem = 2856 KiB, score = 10
    测试数据 #8: TimeLimitExceeded, time = 1046 ms, mem = 2856 KiB, score = 0
    测试数据 #9: TimeLimitExceeded, time = 1109 ms, mem = 2848 KiB, score = 0
    TimeLimitExceeded, time = 3559 ms, mem = 2860 KiB, score = 80

信息

ID
1771
难度
7
分类
模拟 | 数据结构 | 队列 点击显示
标签
递交数
3485
已通过
685
通过率
20%
被复制
12
上传者