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

样例输出

提示

样例解释
显然第一局应该是战斗力为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);
            cout << h << " " << y << " " << cnt  << endl;
        }
        else{
            //如果y胜了，把原来的h放到队尾，然后将y作为基准，他的胜场置为1，
            cout << h << " " << y << " " << cnt  << endl;
            q.pop();
            q.push(h);
            h = y;
            cnt = 1;
        }
    }
    cout << cnt2 << endl;
    return 0;
}

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