首页 > 代码库 > HDU 4585

HDU 4585

2024-07-12 02:42:03   212人阅读

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\n",ma.id,it->id) ;            }            else            {                it1=it ;                it-- ;                if(fabs(it1->lv-ma.lv)>fabs(it->lv-ma.lv))                {                    printf("%d %d\n",ma.id,it->id) ;                }                else                {                    printf("%d %d\n",ma.id,it1->id) ;                }            }            S.insert(ma) ;        }    }    return 0 ;}
View Code

 


联系
我们