瑞士轮(归并排序) - Albert_liu - 博客园

admin 15 0

瑞士轮(归并排序) - Albert_liu - 博客园

#include

#include

using namespace std;

const int maxn=1e6+10;

int s[maxn],n,r,q;

struct node

{

int val,abl,pos;

} e[maxn],temp[maxn],win[maxn],lose[maxn];

bool cmp(node a,node b)

{

if(a.val!=b.val)

return a.val>b.val;

return a.pos

}

void gb(int x,int y)

{

int i=0,j=0,k=1;

while(i

{

if(win[i].val

{

e[k++]=lose[j++];

}

else if(win[i].val>lose[j].val)

{

e[k++]=win[i++];

}

else

{

if(win[i].pos

e[k++]=win[i++];

else

e[k++]=lose[j++];

}

}

while(j

{

e[k++]=lose[j++];

}

while(i

{

e[k++]=win[i++];

}

// for(int i=0; i

// {

// e[star+i]=temp[i];

// }

}

//void GBsort(node *e,int star,int endd)

//{

// if(e==NULL||star>=endd)

// return ;

// int mid=(star+endd)/2;

// GBsort(e,star,mid);

// GBsort(e,mid+1,endd);

// gb(star,mid,endd);

//}

int main()

{

std::ios::sync_with_stdio(false);

cin>>n>>r>>q;

n*=2;

for(int i=1; i<=n; i++)

{

cin>>e[i].val;

e[i].pos=i;

}

for(int i=1; i<=n; i++)

{

cin>>e[i].abl;

}

sort(e+1,e+1+n,cmp);

while(r--)

{

int x=0,y=0;

for(int i=1; i<=n; i+=2)

{

if(e[i].abl>e[i+1].abl)

{

e[i].val++;

win[x++]=e[i];

lose[y++]=e[i+1];

}

else

{

e[i+1].val++;

win[x++]=e[i+1];

lose[y++]=e[i];

}

}

gb(x,y);

}

cout<

return 0;

}

  • 评论列表

留言评论