openjudge 熱血格鬥場

北大 2012研究所學生推免上機考試 F題

OJ送出連結：http://noi.openjudge.cn/ch0309/3343/

描述

為了迎接08年的奧運會，讓大家更加了解各種格鬥運動，facer新開了一家熱血格鬥場。格鬥場實行會員制，但是新來的會員不需要交入會費，而隻要同一名老會員打一場表演賽，證明自己的實力。

我們假設格鬥的實力可以用一個正整數表示，成為實力值。另外，每個人都有一個唯一的id，也是一個正整數。為了使得比賽更好看，每一個新隊員都會選擇與他實力最為接近的人比賽，即比賽雙方的實力值之差的絕對值越小越好，如果有兩個人的實力值與他差别相同，則他會選擇比他弱的那個（顯然，虐人必被虐好）。

不幸的是，Facer一不小心把比賽記錄弄丢了，但是他還保留着會員的注冊記錄。現在請你幫facer恢複比賽紀錄，按照時間順序依次輸出每場比賽雙方的id。

輸入

第一行一個數n(0 < n <=100000)，表示格鬥場新來的會員數（不包括facer）。以後n行每一行兩個數，按照入會的時間給出會員的id和實力值。一開始，facer就算是會員，id為1，實力值1000000000。輸入保證兩人的實力值不同。

輸出

N行，每行兩個數，為每場比賽雙方的id，新手的id寫在前面。

樣例輸入

3
2 1
3 3
4 2
           

樣例輸出

2 1
3 2
4 2
           

解題思路

對C++中STL的map的應用，若用排序等會逾時；

map

源代碼

#include<bits/stdc++.h>
using namespace std;
map<long long,int> M;//能力到id的映射 
map<long long,int>::iterator iter;
map<long long,int>::iterator j;
map<long long,int>::iterator k;
int main(){
    int n;
    M[]=;
    cin>>n;
    int id,cap;
    for(int i=;i<n;i++){
        cin>>id>>cap;
        M[cap]=id;
        /*for(iter=M.begin();iter!=M.end();iter++){
            if(iter->first == cap){
                break;
            }
        }*/ //這樣找會逾時 
        iter=M.find(cap);       
        k=j=iter;       
        if(iter==M.begin()){
            j++;
            cout<<id<<" "<<j->second<<endl;
            continue;
        }
        j++;
        k--;
        int p=k->first;
        int q=j->first;
        if(cap-p<=q-cap){
            cout<<id<<" "<<k->second<<endl; 
        }
        if(cap-p>q-cap){
            cout<<id<<" "<<j->second<<endl;
        }
    }
    return ;
}