HDU 4585 Shaolin（2013杭州邀请赛J题-二分） - c++编程基础

题意：少林一些和尚，每个和尚有一个id和一个分值，按输入顺序一个个和尚进来，一开始寺庙有一个住持，分数无限大，编号为1，然后每个和尚进来后会找寺庙已经有的和尚PK，尽量找分接近的，如果有两个接近的，就找分小的那个，注意和尚ID和分数都不会重复，求出这个PK顺序。

思路：这题用set非常方便，和尚进来一个插入一个，然后利用lower_bound去找答案即可。

代码：

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include
       #include 
       
         using namespace std; const int N = 100005; const int MAXN = 5000005; int n; int vis[MAXN]; struct monks { int id, f; } mo[N]; set
        
          s; int main() { while (~scanf(%d, &n) && n) { s.clear(); for (int i = 0; i < n; i++) { scanf(%d%d, &mo[i].id, &mo[i].f); vis[mo[i].f] = mo[i].id; } printf(%d 1 , mo[0].id); s.insert(mo[0].f); for (int i = 1; i < n; i++) { int ff; set
         
          ::iterator it = s.lower_bound(mo[i].f); int up = *it; if (it == s.begin()) { ff = *it; } else { it--; int down = *it; if (abs(mo[i].f- down) <= abs(mo[i].f - up)) ff = down; else ff = up; } printf(%d %d , mo[i].id, vis[ff]); s.insert(mo[i].f); } } return 0; }