学步园

没想到map还有排序功能，默认按照键值从小到大排序

#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <map>
#include <algorithm>
#include <cstdlib>
using namespace std;

int main() {
    int n;
    int id,g;
    while(scanf("%d",&n) && n) {
        map<int,int>m;
        m[1000000000] = 1;
        for(int i=1; i<=n; ++i) {
            scanf("%d%d",&id,&g);
            printf("%d ",id);
            map<int,int> ::iterator it;
            it = m.lower_bound(g); // 二分找第一个大于等于g的位置，如果没有，则返回末尾位置
            if(it == m.end()) {
                it -- ;
                printf("%d\n",it->second);
            } else {
                if(it == m.begin()) {
                    printf("%d\n",it->second);
                } else {
                    int pos = it->first;
                    int tmp = it->second;
                    it --;
                    printf("%d\n",(pos - g) < (g - it->first) ? tmp : it->second);
                }
            }
            m[g] = id;
        }
    }
    return 0;
}