3

2 1

3 3

4 2

0 

 2 1

3 2

4 2 

大致题意：非常久曾经。少林寺里仅仅有一个等级10^9为方丈，他编号为1，少林寺里有个规矩，每一个新来的和尚都必须和一位等级最接近自己的老（就是比他先来的）和尚进行战斗。后来又来了n个和尚。而且他们按入寺时间依次编号2~n+1，可是时间太久。方丈已经不知道每一个和尚来的时候是跟哪个和尚战斗了，可是他还是记得哪个和尚比哪个和尚先来的。

输入给出n个和尚的编号和他们的等级。

以下就靠你了，让你依次求出每一个和尚进寺是是跟谁战斗的，并输出。

解题思路：直接开数组的话，每次找跟他等级最接近的肯定要排序。眼下知道的最快的快排的也是O(n*lg n)的，因为数据给的是10^5，再加上还要操作，时间已经超了。

所以，得换个思路，那就得用到STL中的map的优势了，也好久没用map做题了。map里的数据会自己主动按键值升序排列。据说map内部的排序是用红黑树（一种不明觉厉的数据结构）实现的。其时间复杂度是O（n）的。同一时候，map里还能够直接用find（）按键值查找键值所在的迭代器，这就太方便了。

详细实现步骤：1.先开个map<int, int> monk,  把方丈的编号id和等级grad在map里建立映射。这里用到了一个小细节。

建立映射能够直接这样写。monk[grad] = id.

2.在循环输入n个和尚的信息，

1）每次输入一个和尚的信息。然后在map里建立映射；

2）此时用find（grad）寻找当前增加的和尚所在的迭代器。

3）然后，考虑当前的迭代器的位置，若是最后一个。就直接输出当前迭代器的前一个；

要是第一个。就输出当前迭代器的后面一个；

要既不是第一个也不是最后一个的话。就比較当前迭代器的first和它前后两迭代器first之间的差值哪个更小，小的输出；

要是两差值一样的话，输出前一个迭代器。

AC代码：

#include <stdio.h>

#include <string.h>

#include <iostream>

#include <algorithm>

#include <vector>

#include <queue>

#include <set>

#include <map>

#include <string>

#include <math.h>

#include <stdlib.h>

#include <time.h>

using namespace std;

#define INF 0x7fffffff

map<int, int> a;      //声明一个map对象

int main()

{

    #ifdef sxk

        freopen("in.txt","r",stdin);

    #endif

    int n, k, g;

    while(scanf("%d",&n)!=EOF && n)

    {

        a[1e9] = 1;       //处理方丈

        for(int i=0; i<n; i++){

            scanf("%d%d", &k, &g);

            a[g] = k;

            map<int, int>::iterator temp = a.find(g);      //按grad查找当前和尚所在的迭代器

            if(temp == a.begin())  printf("%d %d\n", k, (++temp)->second);

            else if(temp == a.end())  printf("%d %d\n", k, (--temp)->second);

            else{

                if(abs((--temp)->first - (++temp)->first) > abs((++temp)->first - (--temp)->first))

                    printf("%d %d\n", k, (++temp)->second);

                else  printf("%d %d\n", k, (--temp)->second);

            }

        }

        a.clear();

    }

    return 0;

}