归并排序 Swiss-system tournament

一直以为，，，只有P党才会苦逼的学各种排序了，自从从Pascal中走出来掉进C++的坑，sort用的是真爽，没想到其实也要学的，那就来(p)review一波吧。

将两个的有序数列合并成一个有序数列，我们称之为"归并"

归并排序便是基于这种思想，有从上往下和从下往上有种实现方法

从上往下具体分为3步：

① 分解 -- 将当前区间一分为二，即求分裂点 mid = (low + high)/2;
② 求解 -- 递归地对两个子区间a[low...mid] 和 a[mid+1...high]进行归并排序。递归的终结条件是子区间长度为1
③ 合并 -- 将已排序的两个子区间a[low...mid]和 a[mid+1...high]归并为一个有序的区间a[low...high]

void msort(int s,int t)
{
	if(s == t)return;
	int mid = (s + t) / 2;
	msort(s , mid);
	msort(mid + 1 , t);
	i = s; j = mid + 1; k = s;
	while(i <= mid&&j <= t)
	{
		if(a[i] <= a[j])
		{
			b[k++] = a[j];
			j++;
		}
		else
		{
			b[k++] = a[i];
			i++;
			//ans=(ans+mid-i+1);
		}
	}
	while(i <= mid)
	{
		b[k++] = a[i];
		i++;
	}
	while(j <= t)
	{
		b[k++] = a[j];
		j++;
	}
	for(int i = s;i <= t;i++)a[i] = b[i];
}

从下往上则是采用递归的方法逐层去分解；（别人家的模板，拿来用一用）

/*
 * 对数组a做若干次合并：数组a的总长度为len，将它分为若干个长度为gap的子数组；
 *             将"每2个相邻的子数组" 进行合并排序。
 *
 * 参数说明：
 *     a -- 待排序的数组
 *     len -- 数组的长度
 *     gap -- 子数组的长度
 */
void mergeGroups(int* a, int len, int gap)
{
    int i;
    int twolen = 2 * gap;    // 两个相邻的子数组的长度

    // 将"每2个相邻的子数组" 进行合并排序。
    for(i = 0; i+2*gap-1 < len; i+=(2*gap))
    {
        merge(a, i, i+gap-1, i+2*gap-1);
    }

    // 若 i+gap-1 < len-1，则剩余一个子数组没有配对。
    // 将该子数组合并到已排序的数组中。
    if ( i+gap-1 < len-1)
    {
        merge(a, i, i + gap - 1, len - 1);
    }
}

/*
 * 归并排序(从下往上)
 *
 * 参数说明：
 *     a -- 待排序的数组
 *     len -- 数组的长度
 */
void mergeSortDown2Up(int* a, int len)
{
    int n;

    if (a==NULL || len<=0)
        return ;

    for(n = 1; n < len; n*=2)
        mergeGroups(a, len, n);
}

Description

A Swiss-system tournament is a tournament which uses a non-elimination format. The first tournament of this type was a chess tournament in Zurich in 1895, hence the name "Swiss system". The tournament will be held based on following rules.

    2*N contestants (indexed 1, 2, ..., 2*N) will have R rounds matches. Before the first round, every contestant has an origin score. After every match, winner will get 1 score and loser will get 0 score. Before and after every round, contestants will be sorted by their scores in descending order. Two contestants with the same score will be sorted by their index with ascending order.

    In every round, contestants will have match based on the sorted list. The first place versus the second place, the third place versus the forth place, ..., the Kth place versus the (K + 1)th place, ..., the (2*N - 1)th place versus (2*N)th place.

   Now given the origin score and the ability of every contestant, we want to know the index of the Qth place contestant. We ensured that there won’t be two contestants with the same ability and the contestant with higher ability will always win the match.

Input

 Multiple test cases. The first line contains a positive integer T (T<=10) indicating the number of test cases.

For each test case, the first line contains three positive integers N (N <= 100,000), R (R <= 50), Q (Q <= 2*N), separated by space.

The second line contains 2*N non-negative integers, s1, s2, ..., s2*N, si (si<= 108) indicates the origin score of constant indexed i.

The third line contains 2*N positive integers, a1, a2, ..., a2*N, ai (ai<= 108) indicates the ability of constant indexed i.

Output

 One line per case, an integer indicates the index of the Qth place contestant after R round matches.

Sample

Input

Copy1
2 4 2
7 6 6 7
10 5 20 15

Output

Copy1

Hint

Source

“浪潮杯”山东省第七届ACM大学生程序设计竞赛

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<string>
#include<queue>
#include<algorithm>
#include<map>
using namespace std;

const int N = 1000010;

struct node
{
    int s,num,b;
}a[2 * N];

int T,n,r,q;
node x[N],y[N];

bool cmp(node k,node l)
{
    if(k.s == l.s) return k.num < l.num;
    return k.s > l.s;
}

void msort()
{
    int lx = -1;
    int ly = -1;
    for(int i = 0;i < 2 * n; i += 2)
    {
        if(a[i].b > a[i + 1].b || (a[i].b == a[i + 1].b && a[i].num < a[i + 1].num))
        {
            x[++lx] = a[i];
            x[lx].s++;
            y[++ly] = a[i + 1];
        }
        else
        {
            x[++lx] = a[i + 1];
            x[lx].s++;
            y[++ly] = a[i];
        }
    }
    int tot = -1;
    int i = 0,j = 0;
    while(i <= lx && j <= ly)
    {
        if(x[i].s > y[j].s ||(x[i].s == y[j].s && x[i].num < y[j].num))
        {
            a[++tot] = x[i];
            i++;
        }
        else
        {
            a[++tot] = y[j];
            j++;
        }
    }
    while(i <= lx)
    {
        a[++tot] = x[i];
        i++;
    }
    while(j <= ly)
    {
        a[++tot] = y[j];
        j++;
    }
   // for(int i = 0;i < 2 * n; ++i) printf("%d ",a[i].num);
    //printf("\n");
}

int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d%d",&n,&r,&q);
        for(int i = 0;i < 2 * n; ++i)
        {
            scanf("%d",&a[i].s);
            a[i].num = i + 1;
        }
        for(int i = 0;i < 2 * n; ++i)
            scanf("%d",&a[i].b);
        sort(a,a + 2 * n,cmp);
        for(int i = 0;i < r; ++i)
            msort();
        //for(int i = 0;i < 2 * n; ++i) printf("%d ",a[i].num);
        printf("%d\n",a[q - 1].num);
    }
    return 0;
}