360笔试第一题----最强的不一定是最后的赢家

傷城~ 2023-02-22 03:59 13阅读 0赞

题目描述  
某赛事有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

public class Main {
    	public static void main(String[] args) {
    		Scanner sc = new Scanner(System.in);
    		int n = sc.nextInt();
    		int m = sc.nextInt();
    		int temp = m; //存储比较次数，若m>n也只需要最多比较n次，
    		if(m>n)	temp = n;
    		Queue<Integer> q = new LinkedList<>();
    		for(int i=0;i<n;i++) q.add(sc.nextInt());
    		int y =0; //存储较大的值
    		int cnt = 0; //连胜次数
    		int count = 0; //总比较次数
    		int h =q.poll(); //存储第一个结点
    		while(cnt<temp) {
    			y = q.peek();
    			if(h>y) {
    				cnt++;
    				q.poll();
    				q.add(y);
    			}else {
    				q.poll();
    				q.add(h);
    				h=y;
    				cnt=1;
    			}
    			count++;
    		}
    		if(m>n) System.out.println(count+m-n);
    		else System.out.println(count);
    	}
    }