360校招——最后赢家(C++)

⭐ 文章链接: www.mengyingjie.com/archives/39/ ⭐

最后赢家

时间限制:C/C++语言 1000MS;其他语言 3000MS
内存限制:C/C++语言 65536KB;其他语言 589824KB

题目描述:

最强的不一定是最后的赢家。

某赛事有n名选手参加,但是不同于其他的比赛,本比赛采取的是擂台赛的形式,n名选手排成一排,每次队伍的第一位和第二位选手进行比赛,输的一方会排到队尾。

当某位选手取得m连胜时,他将成为最后的赢家,且游戏结束,请问截止到游戏结束,共会进行多少次比赛。

两位选手的比赛结果由他们的战斗力决定,n位选手的战斗力是一个1~n的排列,也就是说他们的战斗力两两不同,不会有平局的情况。

输入

输入第一行包含两个正整数n,m,分别代表参赛选手数量和取得连胜的要求。(1<=n<=100000,1<=m<=10^9)

输入第二行包含n个正整数,中间用空格隔开,第i个数表示队伍的第i位选手的战斗力,整体是一个1~n的排列。

输出

输出仅包含一个正整数,表示截止到游戏终止,共进行多少场比赛。

样例输入

4 2
1 3 2 4

样例输出

2

提示

样例解释
显然第一局应该是战斗力为3的选手获胜,第二局同样是战斗力为3的选手获胜,2连胜终止游戏,所以答案是2。此时若修改m为3,则结果是5。

代码

解题思路写在代码的注释里

#include <iostream>
#include <queue>

using namespace std;

int main(){
    //n,m,分别代表参赛选手数量和取得连胜的要求
    //cnt记录作为基准选手的胜场数
    int n, m, h, y, cnt;
    //cnt2表示共进行了多少场比赛
    int cnt2 = 0;
    //定义队列来存储每位选手的战斗力
    queue <int> q;
    cin >> n >> m;
    for(int i = 0; i < n; i++){
        //将战斗力存储在队列中
        cin >> h;
        q.push(h);
    }
    //取出第一个队列当作基准
    h = q.front();
    q.pop();
    //默认胜场为零
    cnt = 0;
    while(cnt < m){
        //一次循环代表进行一场比赛
        cnt2 ++;
        y = q.front();
        //将基准h与现在队首的y相比较
        if(h > y){
            //如果h胜了,他继续当基准,然后他的胜场+1
            cnt++;
            //将队首的y取出,放到队列
            q.pop();
            q.push(y);
        }
        else{
            //如果y胜了,把原来的h放到队尾,然后将y作为基准,他的胜场置为1,
            q.pop();
            q.push(h);
            h = y;
            cnt = 1;
        }
    }
    cout << cnt2 << endl;
    return 0;
}

遇到此类问题,但看了文章还是未解决,
评论或加 QQ:781378815

发表评论

电子邮件地址不会被公开。 必填项已用*标注