sdnu1506 D.Swiss-system tournament(归并排序)

D.Swiss-system tournament

Description

A Swiss-system tournament is a tournament which uses a non-elimination format. The first tournament of this type was a chess tournament in Zurich in 1895, hence the name "Swiss system". The tournament will be held based on following rules.

    2*N contestants (indexed 1, 2, ..., 2*N) will have R rounds matches. Before the first round, every contestant has an origin score. After every match, winner will get 1 score and loser will get 0 score. Before and after every round, contestants will be sorted by their scores in descending order. Two contestants with the same score will be sorted by their index with ascending order.

    In every round, contestants will have match based on the sorted list. The first place versus the second place, the third place versus the forth place, ..., the Kth place versus the (K + 1)th place, ..., the (2*N - 1)th place versus (2*N)th place.

 

   Now given the origin score and the ability of every contestant, we want to know the index of the Qth place contestant. We ensured that there won’t be two contestants with the same ability and the contestant with higher ability will always win the match.

Input

 Multiple test cases. The first line contains a positive integer T (T<=10) indicating the number of test cases.

For each test case, the first line contains three positive integers N (N <= 100,000), R (R <= 50), Q (Q <= 2*N), separated by space.

The second line contains 2*N non-negative integers, s1, s2, ..., s2*N, si (si<= 100000000) indicates the origin score of constant indexed i.

 

The third line contains 2*N positive integers, a1, a2, ..., a2*N, ai (ai<= 100000000) indicates the ability of constant indexed i.

Output

One line per case, an integer indicates the index of the Qth place contestant after R round matches.

Sample Input

1

2 4 2

7 6 6 7

10 5 20 15

 

Sample Output

1

2n个人进行比赛,给出每人的ability&&origin score;每次比赛前后 注意是前后 都会根据目前的分数进行降序排列;比赛时,根据名单,第一名vs第二名 第三名vs第四名……第2n-1名vs第2n名。

问r场比赛之后排名为q的人的id

不难想到结构体排序 于是我理所当然地sort了一遍 果不其然地T了hhhhh

数据范围是1e5  应该用归并排序(挺好orz)

#include <bits/stdc++.h>
using namespace std;
const int N=100005;
struct peo
{
    int sc,ab;
    int num;
}s[2*N],a[N],b[N];
bool cmp(peo x,peo y)
{
    if(x.sc!=y.sc)
        return x.sc>y.sc;
    else if(x.sc==y.sc)
        return x.num<y.num;
}
void solve(int n)
{
    int cnt1=0,cnt2=0;
    for(int i=0;i<n;i+=2)
    {
        if(s[i].ab>s[i+1].ab)///分为两类 胜和败 依次更新score
        {
            a[cnt1]=s[i];
            a[cnt1].sc++;
            cnt1++;
            b[cnt2++]=s[i+1];
        }
        else
        {
            a[cnt1]=s[i+1];
            a[cnt1].sc++;
            cnt1++;
            b[cnt2++]=s[i];
        }
    }
    int cnt=0;
    int i=0,j=0;
    while(i<cnt1&&j<cnt2)///依次比较获胜的人与战败的人的score 更新名单
    {
        if(a[i].sc>b[j].sc||(a[i].sc==b[j].sc&&a[i].num<b[j].num))
            s[cnt++]=a[i++];
        else
            s[cnt++]=b[j++];
    }
    while(i<cnt1)
        s[cnt++]=a[i++];
    while(j<cnt2)
        s[cnt++]=b[j++];
}
int main()
{
    int t,n,r,q;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d%d",&n,&r,&q);
        memset(s,0,sizeof(s));
        for(int i=0;i<2*n;i++)
        {
            scanf("%d",&s[i].sc);
            s[i].num=i+1;
        }
        for(int i=0;i<2*n;i++)
            scanf("%d",&s[i].ab);
        sort(s,s+2*n,cmp);
        while(r--)
            solve(2*n);
        cout<<s[q-1].num<<'\n';
    }
    return 0;
}

 

全部评论

相关推荐

哈哈哈哈哈哈哈哈哈哈这个世界太美好了
凉风落木楚山秋:毕业出路老师不管,你盖个章他好交差就完事了,等你盖完毕业了就不关他事情了
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-09 12:05
点赞 评论 收藏
分享
废物一个0offer:认真的吗二本本科找人工智能岗位
点赞 评论 收藏
分享
07-07 12:47
门头沟学院 Java
码农索隆:竟然还真有卡体检报告的
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-04 15:36
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务