A Singing Contest

  https://www.cnblogs.com/longl/p/9424539.html

思路：

由于每个选手的策略略都是尽可能赢，所以他该认输的时候只能认输。能赢的时候只要选权值大于对方最大值的最小值，大的留在后面不会更差，直接模拟即可。
我的模拟方法是：开一个二维的vector,第一维表示比赛场次，每次比赛完把结果保存到下一层，第二维表示每个歌手（注意不要开小了，我因为开小了TLE好几发，2^14 =16384 ）。
在将结果记录到下一层的同时还要记录原有歌手的标号，以便最后输出结果。

代码：

#include
using namespace std;
const int maxn = 20000;
vector vec[20][maxn];///第一维表示比赛场次，第二维代表歌手
int id[maxn],v, tmp[maxn];
void init()
{
    for(int i=0;i<20;i++)
        for(int j=0;j<maxn;j++)
            vec[i][j].clear();
}
int main()
{
  //  printf("%d\n",1<<14);
    int t;
    scanf("%d",&t);
    for(int cas=1;cas<=t;cas++){
        int n;
        init();
        scanf("%d",&n);
        int cnt = 1<<n;
        for(int i=1;i<=cnt;i++){
            for(int j=1;j<=n;j++){
                scanf("%d",&v);
                vec[1][i].push_back(v);
            }
        }
        for(int i=1;i<=cnt;i++)id[i]=i;
        int singer = cnt;
        for(int i=1;i<n;i++){
            for(int j=1;j<=singer;j+=2){
                set st1,st2;
                set::iterator it;
                for(int k=0;k<vec[i][j].size();k++)st1.insert(vec[i][j][k]);
                for(int k=0;k<vec[i][j+1].size();k++)st2.insert(vec[i][j+1][k]);
                int v1=*(--st1.end());  ///歌手1的最大值
                int v2=*(--st2.end()); ///歌手2的最小值
                if(v1>v2){
                    st1.erase( st1.lower_bound(v2) );  ///在v1中找到比v2大的最小值
                    for(it=st1.begin();it!=st1.end();it++) ///复制到下一层
                        vec[i+1][(j+1)/2].push_back(*it);
                    tmp[(j+1)/2]=id[j];  ///保存原有id
                }else{
                    st2.erase( st2.lower_bound(v1) ); /// ///在v2中找到比v1大的最小值
                    for(it=st2.begin();it!=st2.end();it++)
                        vec[i+1][(j+1)/2].push_back(*it);
                    tmp[(j+1)/2]=id[j+1]; ///保存原有id
                }
            }
            singer>>=1;
            for(int j=1;j<=singer;j++)
                id[j]=tmp[j];
        }
        int ans=0;
        if(vec[n][1][0]>vec[n][2][0]) ans = id[1];
        else ans=id[2];
        printf("Case #%d: %d\n",cas,ans);
    }
    return 0;
}