P7787 [COCI2016-2017#6] Turnir 题解

yydfj · 2021-08-12 20:56:08 · 题解

这是本蒟蒻第九次写的题解，如有错误点请好心指出！

问题简述

这道题我们可以换另一种思路去看待它，就容易理解了：

给你一个长度为 2^{n} 的序列，将它们两两相分，互相作大小比较，小的移除，大的保留，求它们被移除的所在轮数。

解法综述

我们可以先想一下对于从小到大的序列进行题目要求的操作得出的答案会是怎样的，再想一下无序的序列的答案与从小到大的序列的答案有什么规律。

对于从小到大的序列，我们按找题目的要求，可以很快地得出答案。当发现两个数互不相同时，我们就把小的那个数移除，记录它被移除的所在轮数，当发现两个数相等时，我们就将它们同时移除，记录它们被移除的所在轮数。因为该序列时有序的，所以我们不必考虑移除数后要将后面的数移到前面去。

无序的序列的答案其实是由从小到大的序列的答案排列成自己的答案得来的。我们新建一个数组另存该无序的序列，然后将无序的序列排列成从小到大的序列，通过上一段的操作得出答案，最后将答案按新建的数组输出即可。

代码描述

#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
int a[10000005],b[10000005];
int n,m[10000005],x,s;
int main()
{
    cin>>n;
    n=pow(2,n);
    for(int i=1;i<=n;i++) cin>>a[i],b[i]=a[i];//新建一个数组另存该序列
    sort(a+1,a+n+1);//将该序列排列成从小到大的序列
    for(int i=1;i<=n;i++)//进行从小到大的序列操作
    {
        s=0;
        while(a[i]==a[i+1]) i++;
        x=i;
        while(x!=1)
        {
            s++;
            x/=2;
        }
        m[a[i]]=log2(n)-s;//得出从小到大的序列的答案
    }
    for(int i=1;i<=n;i++) cout<<m[b[i]]<<" ";//将答案按新建的数组输出
    return 0;
}