P2828 LJJ打赌

    • 0通过
    • 14提交
  • 题目提供者 eden
  • 评测方式 云端评测
  • 标签 二叉堆 高性能
  • 难度 尚无评定
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    LJJ的伙伴PJY正在看一场赛车比赛。这时,LJJ走了过来。为了说服利欲熏心的LJJ和他一起看,PJY决定与其打赌谁是最终的赢家。不过,PJY绝对不会让自己就这样输钱,他当然得捞一把——他已经事先知道了某一个时刻每个赛车的位置以及它们的速度(速度恒定不变)。因为他也不知道LJJ会赌哪一辆车赢,所以他需要知道按时间顺序前m个超与被超的车辆,因为一旦LJJ所赌的车辆被超,他就不会再和PJY看车赛了,LJJ会知道他必输,且当LJJ看了m次超车之后,他也会疲倦,不再看了。但是,PJY在看车赛呢,这个问题仍然被无(ji)耻(zhi)地交给了你。

    输入输出格式

    输入格式:

    第一行:两个正整数n,m,分别代表赛车数量以及需要输出的超车事件的个数。

    第二行到第n+1行,每行两个整数x,v,在第i+1行表示第i辆车的位置和速度。

    输出格式:

    第一行到第m行:每行2个整数i,j,第k行代表按时间顺序排列的第k个超车事件的超车车辆与被超车车辆。

    (说明:如果超车事件不足m个,则用0+空格+0(”0 0”)来表示。如果超车事件(i1超j1和i2超j2)同时发生,那么:①如果i1的出发位置<i2的出发位置,那么先输出i1超j1;②如果i1,i2为同一辆车,则当j1的出发位置<j2的出发位置,那么先输出i1超j1。)

    数据保证每一辆车的初始位置互不相同。

    输入输出样例

    输入样例#1: 复制
    4 6
    9 1
    6 2
    1 4
    5 3
    输出样例#1: 复制
    4 2
    4 1
    3 2
    3 1
    2 1
    3 4

    说明

    对于30%的数据,1<=n<=5000,1<=m<=5000;

    对于100%的数据,1<=n<=100000,1<=m<=100000.

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。