HDU 4585 Shaolin

利用map的自动排序和lower_bound()

题目链接HDU 4585

题目大意

少林寺选拔和尚，有n个和尚，每个和尚有编号和武力值（所有和尚武力值都不相同），编号代表入寺的时间，少林寺方丈最早，编号为1，武力值为1000000000。每个新和尚入少林寺都要比赛，和老和尚中武力与他最为接近的一个老和尚比赛（反正都确定能进少林寺了），若存在两个老和尚和新和尚的武力值差值一样，则新和尚和两个老和尚中武力值少的一个比赛。少林寺方丈把比赛记录搞丢了，但知道和尚的入寺时间的先后顺序，让你输出每个和尚的编号和与他比赛的和尚的编号。

AC代码

#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <bitset>
#include <string>
#include <vector>
#include <iomanip>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
int main()
{
        int n;
        while(cin>>n,n)
        {
                map<int,int> mp;
                mp.clear();
                map<int,int>::iterator it;
                mp[1000000000]=1;
                for(int k=0;k<n;k++)
                {
                        int a,b;
                        cin>>a>>b;
                        cout<<a<<" ";
                        it=mp.lower_bound(b);
                        if(it==mp.end())
                        {
                                cout<<it->second<<endl;
                        }
                        else if(it==mp.begin())
                        {
                                cout<<it->second<<endl;
                        }
                        else
                        {
                                int y1=it->first;
                                int x1=it->second;
                                it--;
                                int x2=it->second;
                                int y2=it->first;
                                if((b-y2)<=(y1-b))
                                {
                                        cout<<x2<<endl;
                                }
                                else
                                {
                                        cout<<x1<<endl;
                                }
                        }
                        mp[b]=a;
                }
        }
        return 0;
}