[NOIP模拟赛]锦标赛

题目描述 小J喜欢踢足球，经常参加足球锦标赛。现在他想玩一个这样的游戏——锦标赛。他有2N个数字，他想让这些数字来进行pk。首先两两比较，较大的留下，较小的淘汰，如果两者相等，则可以任意选择一个留下，另一个淘汰；然后剩下的数再两两比较。在两两比较时，每个数可以和任意的数pk。如下图所示，为一种pk的方案。可以看出，pk方案形成了一个树型的层次结构。我们把最高层定义为第0层，往下依次为第1层，第2层，……。从下往上，留下的数越来越少。求每个数最高能够留在第几层？ 输入格式 第一行包含整数N（1<=N<=20）

接下来有2N个数，每个数在[1,109]范围内。

输出格式 输出只有一行，包含2N个数，表示每个数最高能够留在第几层。 输入样例2 4 5 3 2 6 4 8 7 1 2 4 3 3 6 4 8 1 输出样例2

1 2 2 1 1 0 1 3 2 1 2 2 1 1 0 3

题解：

如果一个数要保留到尽量高的层次，那么在锦标赛表示的树中，小于等于它的节点都来做它的子树的叶子节点。但因为锦标赛的树是一棵满二叉树，所以如果有x个元素小于等于它，它能达到(int)( log2(x+1) )的高度。

#include<iostream> #include<cstring> #include<cstdlib> #include<cstdio> #include<cmath> #include<algorithm> using namespace std; const int N=1500000; void Getin( int &shu ) { char c; int f=1; shu=0; for( c=getchar(); c<'0' || c>'9'; c=getchar() ) if( c=='-' ) f=-1; for( ; c>='0' && c<='9'; c=getchar() ) shu=shu*10+c-'0'; shu*=f; } int n, m, note[N]; struct node{ int v, id; } num[N]; bool cmp( node a, node b ) { return a.v<b.v; } int main() { Getin(m); n=1<<m; for( int i=1; i<=n; i++ ) Getin( num[i].v ), num[i].id=i; sort( num+1, num+n+1, cmp ); for( int i=1; i<=n; ) { int lst=num[i].v, w=i; for( ; w<=n && lst==num[w].v; w++ ); w--; int p=m-(int)log2(w); for( ; i<=w; i++ ) note[ num[i].id ]=p; } for( int i=1; i<=n; i++ ) { printf( "%d", note[i] ); if( i<n ) putchar(32); else putchar(10); } return 0; }