这题debug了3个小时,当时简直崩溃........
题意 :
有2^n个歌手进行比赛,每位歌手准备好了n首歌,每首歌的愉悦度都不一样,每位歌手都知道对方每首歌的愉悦度,并且愉悦度越高的就会赢,输了的直接淘汰,为了尽可能的多进行几场比赛(赛制为两两相互比赛),歌手每场都会从低到高选出第一个大于对方歌手的歌来进行比赛,对于选值操作在judge函数里,我用的是二分查找的lower_bound()函数,每场输了的人直接将他的vis置为0,赢了的歌手所场完的歌则将它的愉悦度置为-1,然后每次进行judge()操作时都要进行sort排序,愉悦度为-1的歌直接排在前面,对后续的比赛不会影响。
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
using namespace std;
typedef long long int LL;
LL t,m,n,k;
struct node
{
LL song[14];
LL max;
int vis;
} singer[200000];
void judge(int x,int y)
{
LL flag;
sort(singer[x].song,singer[x].song+n);
sort(singer[y].song,singer[y].song+n);
singer[x].max=singer[x].song[n-1];
singer[y].max=singer[y].song[n-1];
if(singer[x].max>singer[y].max)
{
flag=upper_bound(singer[x].song,singer[x].song+n,singer[y].max)-singer[x].song;
singer[x].song[flag]=-1;
singer[y].vis=0;
}
else
{
flag=upper_bound(singer[y].song,singer[y].song+n,singer[x].max)-singer[y].song;
singer[y].song[flag]=-1;
singer[x].vis=0;
}
}
int main()
{
int o=1;
scanf("%lld",&t);
while(t--)
{
scanf("%lld",&n);
int p=pow(2,n);
for(int i=1; i<=p; i++)
{
for(int j=0; j<n; j++)
scanf("%lld",&singer[i].song[j]);
singer[i].vis=1;
}
int num=0,k=n;
while(k--)
{
num = 0;
for(int i=1; i<=p ; i++)
{
if(num!=0&&singer[i].vis)
{
judge(num,i);
num=0;
continue;
}
if(singer[i].vis==1)
num=i;
}
}
for(int i=1; i<=p; i++)
{
if(singer[i].vis)
{
printf("Case #%d: %d\n",o++,i);
break;
}
}
}
return 0;
}