首页 » C++ » C++ 编程题练习-热血格斗场(9-5)

C++ 编程题练习-热血格斗场(9-5)

2016-07-14 15:10:16阅读(1792)

C++ 编程题练习-热血格斗场

来源:coursera c++ pku 第9周编程作业

一、题目

描述

为了迎接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

二、程序
#include <iostream>
#include <map>
#include <cmath>
using namespace std;
int main()
{
    int n;
    cin>>n;
    typedef map<int, int> Map;
    Map mp;
    mp.insert(Map::value_type(1000000000, 1));
    pair<Map::iterator, bool> pairs;
    while(n--){
        int id;
        int power;
        cin>>id>>power;
        //在openjudge提交会超时,不知道为什么
        pairs = mp.insert(make_pair(power, id));
        Map::iterator i = pairs.first;
        Map::iterator i2 = pairs.first;
        int minId;
        if(i==mp.begin()) {
            i++;
            minId = i->second;
        } else if(i==mp.end()){
            i--;
            minId = i->second;
        }else {
            i--;
            i2++;
            minId = i->second;
            if(abs(i->first-power) > abs(i2->first-power)) minId = i2->second;
        }
        cout<<id<<" "<<minId<<endl;;
    }
    return 0;
}

最新发布

CentOS专题

关于本站

5ibc.net旗下博客站精品博文小部分原创、大部分从互联网收集整理。尊重作者版权、传播精品博文,让更多编程爱好者知晓!

小提示

按 Ctrl+D 键,
把本文加入收藏夹