【算法】锦标赛

[编程题] 锦标赛

时间限制：1秒

空间限制：32768K

组委会正在为美团点评CodeM大赛的决赛设计新赛制。

比赛有 n 个人参加（其中 n 为2的幂），每个参赛者根据资格赛和预赛、复赛的成绩，会有不同的积分。比赛采取锦标赛赛制，分轮次进行，设某一轮有 m 个人参加，那么参赛者会被分为 m/2 组，每组恰好 2 人，m/2 组的人分别厮杀。我们假定积分高的人肯定获胜，若积分一样，则随机产生获胜者。获胜者获得参加下一轮的资格，输的人被淘汰。重复这个过程，直至决出冠军。

现在请问，参赛者小美最多可以活到第几轮（初始为第0轮）？

输入描述:

第一行一个整数 n (1≤n≤ 2^20)，表示参加比赛的总人数。

接下来 n 个数字（数字范围：-1000000…1000000），表示每个参赛者的积分。

小美是第一个参赛者。

输出描述:

1	小美最多参赛的轮次。

输入例子:

1
2

4
4 1 2 3

输出例子:

import java.util.Scanner;

public class T2锦标赛 {

	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		while(sc.hasNext()){
			int n=sc.nextInt();
			int my=sc.nextInt();
			if(n==1)//当n=1，时就一个人，直接输出0
				System.out.println(0);
			else{
				int t=1;//最多能排到多少名
				
				for (int i = 1; i < n; i++) {
					int next=sc.nextInt();//后面的n-1个人的积分
					if(next<=my){//只要积分和相等或者小的排名上就可以升一个
						t++;
					}
				}
				
				int ans=0;
				for (; n>=2; n/=2) {//每一轮
					
					System.out.println(t);//输入每轮的排名
					
					if(t>1){//我的排名大于1，就可以进行下一轮
						ans++;
					}else break;
					
					//更新排名情况，看有多少个比我大，然后让他们互相比
					//能留下一半的人，向上取整，如3，留下来的应该是两个人
					double d=n-t;
					d=d/2;
					t= n/2-(int)Math.ceil(d);
				}
				System.out.println(ans);
			}
		}
	}
}