HDU 4585

http://acm.hdu.edu.cn/showproblem.php?pid=4585

从原来的人中找出战斗数值最接近的，输出他们两人的序号

要在logn的复杂度完成查找，我用的是set，当然用map也可以，两个内部都是红黑树实现

水题一道

#include <iostream>
#include <cstdio>
#include <set>
#include <cmath>
using namespace std ;
struct node
{
    int id,lv ;
    friend bool operator <(node a,node b)//按lv从小到大排序 
    {
        return a.lv>b.lv;
    }
} ;
int main()
{
    int n ;
    set <node> S ;
    while(~scanf("%d",&n),n)
    {
        S.clear() ;
        node ma ;
        ma.id=1 ;ma.lv= 1000000000 ;
        S.insert(ma) ;
        while(n--)
        {
            scanf("%d%d",&ma.id,&ma.lv) ;
            set <node>::iterator it,it1 ;
            it=S.lower_bound(ma) ;
            if(it==S.begin())
            {
                printf("%d %d
",ma.id,it->id) ;
            }
            else
            {
                it1=it ;
                it-- ;
                if(fabs(it1->lv-ma.lv)>fabs(it->lv-ma.lv))
                {
                    printf("%d %d
",ma.id,it->id) ;
                }
                else
                {
                    printf("%d %d
",ma.id,it1->id) ;
                }
            }
            S.insert(ma) ;
        }
    }
    return 0 ;
}