STL大法好，不用手打归并排序，
本题中使用sort()会TLE，应该用stable_sort()
原因：每一轮过后，每个人的排名不会变化太大，
sort()排序时会把元素打乱，而stable_sort()不会把元素打乱。
时间复杂度O(r N logN)

#include<cstdio>
#include<algorithm>
using namespace std;

const int maxn=200020;
int n,r,q,w[maxn];

struct Node
{
    int id,s;
    void read(int i)
    {
        id=i;
        scanf("%d",&s);
    }
    bool operator < (const Node & x) const 
    {
        return s>x.s||s==x.s&&id<x.id;
    }
}a[maxn];

int main()
{
    scanf("%d%d%d",&n,&r,&q);
    n*=2;
    for (int i=0;i<n;i++) a[i].read(i);
    for (int i=0;i<n;i++) scanf("%d",&w[i]);
    sort(a,a+n);
    for (int i=0;i<r;i++)
    {
        for (int j=0;j<n;j+=2)
            a[j+(w[a[j].id]<w[a[j+1].id])].s++;//胜者加分 
        stable_sort(a,a+n);//归并排序，注意：此处用sort()会TLE
    }
    printf("%d\n",a[q-1].id+1);//排名从0开始 
    
    return 0;
}

使用stable_sort()
测试数据 #6: Accepted, time = 218 ms, mem = 3692 KiB, score = 10
测试数据 #7: Accepted, time = 328 ms, mem = 4468 KiB, score = 10
测试数据 #8: Accepted, time = 437 ms, mem = 4468 KiB, score = 10
测试数据 #9: Accepted, time = 515 ms, mem = 4472 KiB, score = 10
Accepted, time = 1669 ms, mem = 4472 KiB, score = 100
.
.
使用sort()
测试数据 #6: Accepted, time = 515 ms, mem = 2856 KiB, score = 10
测试数据 #7: Accepted, time = 734 ms, mem = 2856 KiB, score = 10
测试数据 #8: TimeLimitExceeded, time = 1046 ms, mem = 2856 KiB, score = 0
测试数据 #9: TimeLimitExceeded, time = 1109 ms, mem = 2848 KiB, score = 0
TimeLimitExceeded, time = 3559 ms, mem = 2860 KiB, score = 80

stl大法好
```
#include<iostream>
#include<queue>
#include<algorithm>
#include<vector>
#include<cstdio>
#include<cstring>

using namespace std;
struct Player{
int s,w,num;
bool operator < (const Player& rhs) const {
if (s == rhs.s) return num < rhs.num;
else return s > rhs.s;
}
};
const int maxn = 100000 + 5;
const int INF = 100000000;
int n, r, q;
int s[maxn * 2], w[maxn * 2];
vector<Player> list;
vector<Player> winner;
vector<Player> loser;
int main(){
freopen("in.txt", "r", stdin);
cin>> n >> r >> q;
for(int i = 1; i <= 2 * n; i++) scanf("%d", &s[i]);
for(int i = 1; i <= 2 * n; i++) {
scanf("%d", &w[i]);
list.push_back((Player){s[i], w[i],i});
}
sort(list.begin(), list.end());

for(int j = 1; j <= r; j++){
//模拟比赛
for(int i = 0; i < n; i++){
if(list[2*i].w > list[2*i+1].w){
list[2*i].s++;
winner.push_back(list[2*i]);
loser.push_back(list[2*i+1]);
}
else{
list[2*i+1].s++;
loser.push_back(list[2*i]);
winner.push_back(list[2*i+1]);
}
}
//归并排序
list.clear();

int w = 0, l = 0;
while(w < winner.size() && l < loser.size())
list.push_back((winner[w] < loser[l])? winner[w++] : loser[l++]);
while(w < winner.size())
list.push_back(winner[w++]);
while(l < loser.size())
list.push_back(loser[l++]);

winner.clear(); loser.clear();
}
cout << list[q-1].num << endl;

return 0;
}
```

#include <cstdio>
#include <algorithm>
using namespace std;

typedef long long ll;
const int MAX_N = 200000;
int n, r, q;
struct xs
{
    int s, w, no;
};
bool comp(const xs &a, const xs &b)
{
    if (a.s != b.s) {
        return a.s > b.s;
    }
    return a.no < b.no;
}
xs xsm[MAX_N], helper[MAX_N];

int main()
{
    scanf("%d %d %d", &n, &r, &q);
    for (int i = 0; i < 2 * n; i++) {
        scanf("%d", &xsm[i].s);
        xsm[i].no = i;
    }
    for (int i = 0; i < 2 * n; i++) {
        scanf("%d", &xsm[i].w);
    }

    sort(xsm, xsm + 2 * n, comp);
    while (r--) {
        int l = 0, r = n;
        for (int i = 0; i < n; i++) {
            int win;
            win = (xsm[2 * i].w > xsm[2 * i + 1].w) ? 2 * i : 2 * i + 1;
            xsm[win].s++;
            helper[l++] = xsm[win];
            helper[r++] = xsm[4 * i + 1 - win];
        }
        l = 0; r = n;
        int tail = 0;
        while (l < n && r < 2 * n) {
            if (comp(helper[l], helper[r])) {
                xsm[tail++] = helper[l++];
            }
            else {
                xsm[tail++] = helper[r++];
            }
        }
        while (l < n) {
            xsm[tail++] = helper[l++];
        }
        while (r < 2 * n) {
            xsm[tail++] = helper[r++];
        }
    }
    printf("%d\n", xsm[q - 1].no + 1);
}

快排+并归
注意是降序排列。。。开始写升序写惯了然后WA
```pascal
uses math;
type player=record
s,k,w:longint;
end;
var n,q,r,i,j,p1,p2:longint;
a,wr,lr:array[0..200000] of player;

procedure swap(x,y:longint);
var tmp:player;
begin
tmp:=a[x];a[x]:=a[y];a[y]:=tmp;
end;

procedure qsort(b,e:longint);
var i,j,r:longint;
begin
if b>=e then exit;
r:=random(e-b)+b;
swap(r,e);
i:=b-1;
for j:=b to e-1 do
if (a[j].s>a[e].s) or ((a[j].s=a[e].s) and (a[j].k<a[e].k)) then begin
inc(i);
swap(i,j);
end;
swap(i+1,e);
qsort(i+2,e);
qsort(b,i);
end;

begin
read(n,r,q);
for i:=1 to 2*n do begin
a[i].k:=i;
read(a[i].s);
end;
for i:=1 to 2*n do read(a[i].w);
qsort(1,2*n);

for j:=1 to r do begin
for i:=1 to n do
if a[i*2-1].w>a[i*2].w then begin
inc(a[i*2-1].s);
wr[i]:=a[i*2-1];lr[i]:=a[i*2];
end else begin
inc(a[i*2].s);
wr[i]:=a[i*2];lr[i]:=a[i*2-1];
end;
p1:=1;p2:=1; //union
for i:=1 to 2*n do
if (p1<=n) and (
(p2>n) or
(wr[p1].s>lr[p2].s) or
((wr[p1].s=lr[p2].s) and (wr[p1].k<lr[p2].k))
)
then begin
a[i]:=wr[p1];
inc(p1);
end else begin
a[i]:=lr[p2];
inc(p2);
end;
end;
write(a[q].k);
end.
```

测试数据 #0: Accepted, time = 0 ms, mem = 5248 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 5248 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 5248 KiB, score = 10
测试数据 #3: Accepted, time = 15 ms, mem = 5248 KiB, score = 10
测试数据 #4: Accepted, time = 31 ms, mem = 5252 KiB, score = 10
测试数据 #5: Accepted, time = 62 ms, mem = 5244 KiB, score = 10
测试数据 #6: Accepted, time = 93 ms, mem = 5248 KiB, score = 10
测试数据 #7: Accepted, time = 203 ms, mem = 5248 KiB, score = 10
测试数据 #8: Accepted, time = 250 ms, mem = 5248 KiB, score = 10
测试数据 #9: Accepted, time = 218 ms, mem = 5244 KiB, score = 10
Accepted, time = 872 ms, mem = 5252 KiB, score = 100

http://www.cnblogs.com/Coolxxx/p/5343273.html

只用一次快排，然后用归并排序的思想，算法复杂度O( N*r )
/*

Author : Slience_K
Belong : C++
Pro : NOIP 2011

*/
#include <cstdio>
#include <cstring>
#include <algorithm>
#define sz 100005
using namespace std;
struct Node{
int mark , s , order;
bool operator < ( const Node &x ) const {
if ( mark == x.mark ) return order < x.order;
else return mark > x.mark;
}
};
Node a[ 2 * sz ] , loser[ 2 * sz ] , winner[ 2 * sz ];
int n , r , q , s , t , k , tl , tw;
int main(){

scanf( "%d%d%d" , &n , &r , &q );
for( int i = 1 ; i <= 2 * n ; i++ ){
scanf( "%d" , &a[ i ].mark );
a[ i ].order = i;
}
for( int i = 1 ; i <= 2 * n ; i++ )
scanf( "%d" , &a[ i ].s );
sort( a + 1 , a + 2 * n + 1 );
for( int i = 1 ; i <= r ; i++ ){
tl = 0;
tw = 0;
for( int j = 1 ; j <= n ; j++ ){
s = 2 * j - 1;
t = 2 * j;
if ( a[ s ].s > a[ t ].s ){
a[ s ].mark++;
winner[ ++tw ] = a[ s ];
loser[ ++tl ] = a[ t ];
}
else{
a[ t ].mark++;
winner[ ++tw ] = a[ t ];
loser[ ++tl ] = a[ s ];
}
}
k = 0;
tl = 1;
tw = 1;
while( tl <= n && tw <= n ){
if ( winner[ tw ].mark > loser[ tl ].mark ){
a[ ++k ] = winner[ tw ];
tw++;
}
else if ( winner[ tw ].mark < loser[ tl ].mark ){
a[ ++k ] = loser[ tl ];
tl++;
}
else{
if ( winner[ tw ].order < loser[ tl ].order )
a[ ++k ] = winner[ tw++ ];
else a[ ++k ] = loser[ tl++ ];
}
}
while( tl <= n )
a[ ++k ] = loser[ tl++ ];
while( tw <= n )
a[ ++k ] = winner[ tw++ ];
}
printf( "%d" , a[ q ].order );

return 0;
}

本人第一次上传题...

不过应该没错，毕竟是原题嘛！

实在不会的上百度，谷歌也行，但不要用测试数据打表！！！

虽然此题很难（FOR biginner),但希望大家认真想

快排，只对一部分人（大概是2r*1000）进行积分，60分。
实质上，只需要使用一次快排就可以了，比赛了，分别用a，b两个数组来储存胜利者和失败，当一轮比赛过后，再将这两个数组进行归并操作，合并为一个ans数组，可以大大节省时间。
ans[i,1]表示排名第i的选手的积分，ans[i,2]表示实力值，ans[i,3]表示他的编号。a储存胜利者，b储存失败者。

#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;
int N,R,Q;
struct node
{
int s,w,p;
}t[210000],first[210000],second[210000];
bool cmp(node x,node y)
{
if(x.s<y.s) return false;
if(x.s>y.s) return true;
if(x.p<y.p) return true;
return false;
}
void input()
{
scanf("%d%d%d",&N,&R,&Q);
for(int i=1;i<=2*N;i++) scanf("%d",&t[i].s);
for(int i=1;i<=2*N;i++) scanf("%d",&t[i].w);
for(int i=1;i<=2*N;i++) t[i].p=i;
}
void work()
{
sort(t+1,t+2*N+1,cmp);
while(R--)
{
for(int i=1;i<=2*N;i+=2)
if(t[i].w>t[i+1].w)
{
t[i].s++;
first[(i+1)/2]=t[i];
second[(i+1)/2]=t[i+1];
}
else
{
t[i+1].s++;
first[(i+1)/2]=t[i+1];
second[(i+1)/2]=t[i];
}
int x=1,y=1,cnt=0;
while(x<=N && y<=N)
if(first[x].s>second[y].s)
t[++cnt]=first[x++];
else if(first[x].s<second[y].s)
t[++cnt]=second[y++];
else
{
if(first[x].p<second[y].p)
t[++cnt]=first[x++];
else
t[++cnt]=second[y++];
}
while(x<=N) t[++cnt]=first[x++];
while(y<=N) t[++cnt]=second[y++];
//sort(t+1,t+2*N+1,cmp);
}
printf("%d\n",t[Q].p);
}

int main()
{
input();
work();
return 0;
}

#include<stdio.h>
#include<stdlib.h>
#include<iostream>
using namespace std;
//定义<选手>结构体
struct player
{
int score, weight, num; //得分，能力，编号
}all[200000], win[100000], lose[100000];
//all：所有选手的数组
//win：每一轮下来之后，胜者组成一组
//lose：负者组成一组

//为了调用qsort库函数(快排)，自己定义的比较大小函数
//需要注意的是，qsort函数默认从小到大排序，所以这里在比较的时候要反过来。具体表现就是如果a>b,那么返回一个负数
//写的有点复杂，其实原理很简单。
//请参照注释掉的代码理解，过程过程一样，只不过后者用了指针
/*
int cmp(player a, player b){
if(a.score == b.score)
return a.num > b.num ? 1 : -1;
else
return a.score > b.score ? -1 : 1;
}
*/
int cmp(const void *a, const void *b){
if(((struct player *)a)->score == ((struct player *)b)->score)
return ((struct player *)a)->num > ((struct player *)b)->num ? 1 : -1;
else
return ((struct player *)a)->score > ((struct player *)b)->score ? -1 : 1;
}

int main(){
int N, R, Q;
int i, j, ww, ll;
scanf("%d%d%d", &N, &R, &Q);
for(i=0; i<2*N; i++){ //读入初始得分
scanf("%d", &all[i].score);
all[i].num = i+1; //这里注意：编号是从1开始，但是我们的i是从0开始
}
for(i=0; i<2*N; i++) //读入能力值
scanf("%d", &all[i].weight);
//---------------------------------------
qsort(all, 2*N, sizeof(struct player), cmp); //快速排序
//---------------------------------------
for(i=0; i<R; i++){ //模拟进行 R 轮比赛
//1. 先抽取所有的胜者 和 所有的负者 分别存在win和lose数组里
for(j=0; j<2*N; j+=2){
if(all[j].weight >= all[j+1].weight){ //题目中说能力值大的一定赢
win[j/2] = all[j]; win[j/2].score += 1; //赢的+1
lose[j/2] = all[j+1];
}
else{
win[j/2] = all[j+1]; win[j/2].score += 1;
lose[j/2] = all[j];
}

}
//---
//2.根据抽取出的两个数组，归并排序，再存到原来的数组all里
//归并排序的过程你可以这样想：你有两串糖葫芦，每一串从上到下都是上边的比下边的大(有序).
//你现在要吃掉它们，但是你总是想先吃最大的。
j=0;
ww=0; ll=0;
while(ww<N && ll<N){
if(win[ww].score > lose[ll].score)
all[j++]=win[ww++];
else if(win[ww].score < lose[ll].score)
all[j++]=lose[ll++];
else if(win[ww].score == lose[ll].score && win[ww].num < lose[ll].num)
all[j++]=win[ww++];
else
all[j++]=lose[ll++];
}
//现在，应该是有一串糖葫芦吃完了吧，你只能把另一串按顺序吃掉啦
//对all赋值的过程就是吃糖葫芦的过程，那么也可以假设win是左手拿着的，lose是右手拿着的吧
if(ww >= N) //左手吃光了
while(ll<N)
all[j++]=lose[ll++];
else //或者右手吃光了
while(ww<N)
all[j++]=win[ww++];
}
//----------------------------------------
printf("%d\n", all[Q-1].num); //还是一样，我们存的时候序列id从0开始，所以在有序的数组all里，第Q名选手就是all[Q-1]
return 0;
}

​

P1771瑞士轮
Accepted

记录信息

评测状态 Accepted
题目 P1771 瑞士轮
递交时间 2014-10-23 16:38:16
代码语言 C++
评测机 上海红茶馆
消耗时间 2264 ms
消耗内存 5252 KiB
评测时间 2014-10-23 16:38:19

评测结果

编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 5248 KiB, score = 10

测试数据 #1: Accepted, time = 0 ms, mem = 5252 KiB, score = 10

测试数据 #2: Accepted, time = 0 ms, mem = 5252 KiB, score = 10

测试数据 #3: Accepted, time = 15 ms, mem = 5248 KiB, score = 10

测试数据 #4: Accepted, time = 78 ms, mem = 5248 KiB, score = 10

测试数据 #5: Accepted, time = 203 ms, mem = 5252 KiB, score = 10

测试数据 #6: Accepted, time = 281 ms, mem = 5248 KiB, score = 10

测试数据 #7: Accepted, time = 484 ms, mem = 5244 KiB, score = 10

测试数据 #8: Accepted, time = 578 ms, mem = 5244 KiB, score = 10

测试数据 #9: Accepted, time = 625 ms, mem = 5244 KiB, score = 10

Accepted, time = 2264 ms, mem = 5252 KiB, score = 100

代码

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <algorithm>

using namespace std;

int n , r , q;
int i;
int k , l , tk , tl;

struct person
{
int power;
int score;
int num;
};

person p[200000 + 2];
person a[100000 + 2];
person b[100000 + 2];

bool great( person a , person b )
{
if( a.score > b.score )
return 1;
if( a.score == b.score )
if( a.num < b.num )
return 1;
return 0;
}

void Qsort( int a[] , int i , int j )
{
if( i >= j )
return;
int l = i;
int r = j;
int key = a[i];
while( l < r )
{
while( l < r && a[r] >= key )
r--;
a[l] = a[r];
while( l < r && a[l] <= key )
l++;
a[r] = a[l];
}
a[l] = key;
Qsort( a , i , l - 1 );
Qsort( a , l + 1 , j );
}

int main()
{
while( scanf( "%d %d %d" , &n , &r , &q ) != EOF )
{
for( i = 0 ; i < 2 * n ; i++ )
scanf( "%d" , &p[i].score );
for( i = 0 ; i < 2 * n ; i++ )
{
scanf( "%d" , &p[i].power );
p[i].num = i + 1;
}
sort( p , p + 2 * n , great );
while( r-- )
{
memset( a , -1 , sizeof( a ) );
memset( b , -1 , sizeof( b ) );
k = 0;
l = 0;
for( i = 0 ; i < n ; i++ )
{
if( p[ 2 * i ].power >= p[ 2 * i + 1 ].power )
{
p[ 2 * i ].score++;
a[ k++ ] = p[ 2 * i ];
b[ l++ ] = p[ 2 * i + 1 ];
}
else
{
p[ 2 * i + 1 ].score++;
a[ k++ ] = p[ 2 * i + 1 ];
b[ l++ ] = p[ 2 * i ];
}
}
tk = 0;
tl = 0;
for( i = 0 ; i < n * 2 ; i++ )
{
if( a[tk].score > b[tl].score )
p[i] = a[ tk++ ];
else if( a[tk].score < b[tl].score )
p[i] = b[ tl++ ];
else
if( a[tk].num < b[tl].num )
p[i] = a[ tk++ ];
else
p[i] = b[ tl++ ];
}
}
cout << p[q - 1].num << endl;
}
return 0;
}

交了n次边错边改。。。别笑我T T
代码加注释：
#include <stdio.h>
#include <algorithm>

using namespace std;

//思路：
//先建个struct方便用STL-sort进行第一次比赛的sort
//之后的比赛用模拟的方法进行排序
//但考虑到每一个人的名词变动是有限的
//对于所有在当局比赛击败对手的人，他们的相对次序是不变的
//同样，对于所有在当局比赛输给对手的人，他们的相对次序也是不变的
//用两个队列保存赢的和输的人，可以实现当局比赛O(n)的排序

struct player{
int num,s,w;
}pl[200010];

player winner[100005],loser[100005];

bool cmp(player a, player b){
return a.s==b.s ? a.num<b.num : a.s>b.s;
}

int main(){
int n,r,q;
int i;
int wp,lp;//winner和loser队列的"指针"

while( ~scanf("%d%d%d",&n,&r,&q) ){
for(i=1;i<=2*n;i++){
scanf("%d",&pl[i].s);
pl[i].num=i;
}
for(i=1;i<=2*n;i++)
scanf("%d",&pl[i].w);

sort(pl+1,pl+2*n+1,cmp);//第一次比赛后排序

//比赛用模拟的方法进行，从高到低排序
while( r-- ){
for(i=1;i<=n;i++){//写入winner loser队列
if( pl[i*2-1].w > pl[i*2].w )
;
else
swap(pl[i*2-1],pl[i*2]);
pl[i*2-1].s++;
winner[i] = pl[i*2-1];
loser[i] = pl[i*2];
}

//读取两个队列，重新组成pl队列
//init
wp=1;
lp=1;
for(i=1;i<=2*n;i++){
if( wp<=n && ( lp>n || winner[wp].s > loser[lp].s || (winner[wp].s == loser[lp].s && winner[wp].num < loser[lp].num) ) ){
//对于wp,lp的越界要特别注意！！！！
pl[i] = winner[wp];
wp++;
}else{
pl[i] = loser[lp];
lp++;
}
}
}

printf("%d\n",pl[q].num);
}

return 0;
}

思路如下:
首先第一场比赛前要排序,这个自然是用库中的qsort了.
然后就是每一轮比赛之后又要重新排序.这下可不能用qsort了,虽然qsort很quickly了,但是你老叫人家也会超时的.观察可以发现.由于赢了都是+1分,输了都是不加分.所以赢得人和输了的人排序后的相对位置应该不变。所以也就是说赢得人依然是有序的。输的人也是有序的，然后问题就转化为合并两个有序数组为一个有序的了。肯定是二分法登场了。
时间估计会超时，还是要先试试为好。经本地测试，最慢的一个点（也就是说最后一个最大的点）是2秒多一点。
果然还是有点悬,然后又想到,
i后两三个的组人就有可能比i更小了,我却还饶了基本上大半个圈子.从基本上n个数去二分查找.虽然是logn,但还是超了呀.何不先和后面的第三个(LL)比较,然后决定二分查找的范围呢?
后来终于优化到1.05s左右,但是不放心又加了一个比较LLL
代码如下,可千万不要直接复制.仅供参考学习,若是直接复制,然后ce了,不要怨我

#include<stdio.h>
#include<cstdlib>
#include<cstring>
#include<cmath>
#define N 200000
#define LL 3
#define LLL 10
int n,m,q;
struct person{
int n;
int por;
int sce;
};
//int poer[N],score[N];
struct peron p[N];
int win[N],lse[N],rank[N],r,f;
void init()
{
scanf("%d%d%d",&n,&m,&q);
int i,j;
j = n<<1; q--;
for (i = 0;i < j;i++) scanf("%d",&p[i].score);
for (i = 0;i < j;i++) {
scaf("%d",p[i].power); p[i].n = i;
rank[i] = i;
}
}
int cmp(const void *aa,const void *bb)
{
struct person static *a,*b;
a= (struct person*)aa; b = (struct person*)bb;
if (a->score == b->score)
return a->n-b->n;
else
return b->score-a->score;
}
void fight()
{
int static i;
for (i = 0;i < n;i++) {
//i*2 i*2+1
if (p[rank[2*i]].power > p[rank[2*i+1]].power) {
win[i] = rank[2*i]; lose[i] = rank[2*i+1];
p[rank[2*i]].score++;
} else {
win[i] = rank[2*i+1]; lose[i] = rank[2*i];
p[rank[2*i+1]].score++;
}
}
}
int key,u,v,mid;
int find()//二分查找,返回值f满足 p[f+1]<p[key]<p[f]
{
mid = (u+v)/2;
if (cmp(&p[key],&p[win[mid]]) < 0) {
if (mid-1 >= u) {
v = mid-1;
return find();
}
else
return mid;
} else {
if (mid+1 <= v) {
u = mid+1;
return find();
}
else
return mid+1;
}
}
void insert(int *rank,int *win,int lose)
{
//score n
int i,rr;
for (i = f = r = 0;i < n;i++) {
key = lose[i]; u = f;
if ((f+LL < n) && (cmp(&p[key],&p[win[f+LL]]) < 0)) v = f+LL-1; //看后面第三个是否比它更小,是就缩小查找范围.算一种剪枝吧,虽然搜索中我好像很少用.
else if ((f+LLL < n) && (cmp(&p[key],&p[win[f+LLL]]) < 0)) v = f+LLL-1; //理由同上
else v = n-1;
rr = find();
memcpy(rank+r,win+f,sizeof(int)(rr-f));
r += rr-f; rank[r++] = lose[i]; f = rr;
}
rr = n; memcpy(rank+r,win+f,sizeof(int)*(rr-f));
}
int main()
{
int i;
init();
qsort(p,n*2,sizeof(struct person),cmp);
for (i = 0;i < m;i++) {
fight();
insert(rank,win,lose);
}
printf("%d",p[rank[q]].n+1);
return 0;
}

尼玛真吭，N范围是100000，但是还要*2啊，60分的同志写归并的注意了

写一个优先队列或者是堆 然后直接模拟即可。。。
貌似用STL有点。。。。。。
#include <cstdio>
#include <queue>

using namespace std;

#define MAXN 100001

struct saver{
int n;
int v;
};

struct cmp{
bool operator()(saver x,saver y){
if (x.v<y.v){
return true;
}
if (x.v>y.v){
return false;
}
if (x.n>y.n){
return true;
}
return false;
}
};

priority_queue<saver,vector<saver>,cmp>Num;

int n,r,q;
int w[MAXN*2];

int main(){
scanf("%d %d %d",&n,&r,&q);
for (int i=0;i<n*2;i++){
int x;
scanf("%d",&x);
saver y;
y.n=i+1;
y.v=x;
Num.push(y);
}
for (int i=0;i++<n*2;){
scanf("%d",&w[i]);
}
while (r--){
saver q[MAXN*2];
for (int i=0;i<n;i++){
saver x,y;
x=Num.top();
Num.pop();
y=Num.top();
Num.pop();
if (w[x.n]>w[y.n]){
x.v++;
} else y.v++;
q [i*2]=x;
q [i*2+1]=y;
}
for (int i=0;i<n*2;i++){
Num.push(q[i]);
}
}
saver ans;
while (q--){
ans=Num.top();
Num.pop();
}
printf("%d\n",ans.n);
return 0;
}

NOIP普及组NO。3

类型+模拟轻松pass

常可，你牛啊

你出的？

编译成功

Free Pascal Compiler version 2.6.4 [2014/03/06] for i386
Copyright (c) 1993-2014 by Florian Klaempfl and others
Target OS: Win32 for i386
Compiling foo.pas
foo.pas(14,7) Warning: Variable "sum" does not seem to be initialized
foo.pas(5,5) Note: Local variable "c" not used
Linking foo.exe
27 lines compiled, 0.1 sec , 28256 bytes code, 1628 bytes data
1 warning(s) issued
1 note(s) issued
测试数据 #0: RuntimeError, time = 0 ms, mem = 8640 KiB, score = 0
测试数据 #1: RuntimeError, time = 0 ms, mem = 8640 KiB, score = 0
测试数据 #2: RuntimeError, time = 15 ms, mem = 8636 KiB, score = 0
测试数据 #3: RuntimeError, time = 281 ms, mem = 8636 KiB, score = 0
测试数据 #4: TimeLimitExceeded, time = 1015 ms, mem = 8640 KiB, score = 0
测试数据 #5: TimeLimitExceeded, time = 1015 ms, mem = 8640 KiB, score = 0
测试数据 #6: TimeLimitExceeded, time = 1015 ms, mem = 8636 KiB, score = 0
测试数据 #7: WrongAnswer, time = 375 ms, mem = 8640 KiB, score = 0
测试数据 #8: WrongAnswer, time = 578 ms, mem = 8636 KiB, score = 0
测试数据 #9: WrongAnswer, time = 843 ms, mem = 8636 KiB, score = 0
TimeLimitExceeded, time = 5137 ms, mem = 8640 KiB, score = 0
代码
program nihaowoshituerbi;
var
a:array[0..10000,0..100,1..2] of longint;
b:array[0..100] of longint;
i,j,c,d,n,m,k,now,sum:longint;
begin
read(n,m);
for i:=1 to n do
for j:=0 to m-1 do
read(a[i,j,1],a[i,j,2]);
read(now);
for i:=1 to n do
begin
sum:=(sum+a[i,now,2]) mod 20123;
d:=a[i,now,2];
k:=0;
for j:=now to m-1 do
if a[i,j,1]=1 then begin inc(k);b[k]:=j;
end;
for j:=0 to now-1 do
if a[i,j,1]=1 then begin inc(k);b[k]:=j;
end;
d:=d mod k;
if d=0 then d:=k;
now:=b[d];
end;
write(sum);
end.