首页 > 代码库 > HDU 4585 Shaolin(map应用+二分)

HDU 4585 Shaolin(map应用+二分)

题目大意:原题链接

初始少林最开始只有一个老和尚,很多人想进少林,每个人有一个武力值,若某个人想进少林,必须先与比他早进去的并且武力值最接近他的和尚比武,

如果接近程度相同则选择武力值比他小的,按照进入少林的先后顺序,求出每个和尚进去的时候应当和哪个和尚比武。

#include<map>
#include<iostream>
using namespace std;
int main()
{
    int n,id,g;
    map<int,int>::iterator it,p1,p2;
    while(scanf("%d",&n),n){
        map<int,int> m;
        m[1000000000]=1;
        while(n--){
            scanf("%d%d",&id,&g);//first为战斗值,second为编号 
            it=m.lower_bound(g);
            if(it==m.begin())
                cout<<id<< <<it->second<<endl;
            else{
                p1=it,p2=--it;
                if(p1->first-g>=g-p2->first)//等号是为了当两边相等时输出战斗值较低的  
                    cout<<id<< <<p2->second<<endl;
                else
                    cout<<id<< <<p1->second<<endl;
            }
            m[g]=id;//g为战斗值,id为编号
        }
    }    
} 

 

HDU 4585 Shaolin(map应用+二分)