P2107 小Z的AK计划

    • 519通过
    • 1.9K提交
  • 题目提供者 LittleZ
  • 评测方式 云端评测
  • 标签 二叉堆 高性能
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    在小Z的家乡,有机房一条街,街上有很多机房。每个机房里都有一万个人在切题。小Z刚刷完CodeChef,准备出来逛逛。

    机房一条街有 n 个机房,第 i 个机房的坐标为 xi ,小Z的家坐标为 0。小Z在街上移动的速度为1,即从 x1 到 x2 所耗费的时间为 |x1 − x2|。 每个机房的学生数量不同,ACM 题目水平也良莠不齐。小Z到达第 i 个机房后,可以花 ti 的时间想题,然后瞬间 AK;当然,也可以过机房而不入。

    小Z现在只有 m 个单位时间,之后他就该赶着去打 Codeforces 了。现在他想知道自己最多能在多少个机房 AK,希望你帮帮他。

    输入输出格式

    输入格式:

    第一行包含两个整数 n,m。

    接下来 n 行,每行包含两个整数 xi,ti 。

    输出格式:

    第一行包含一个整数,表示小Z最多能 AK 的机房数量。

    输入输出样例

    输入样例#1: 复制
    2 10
    1 100
    5 5
    输出样例#1: 复制
    1

    说明

    【数据规模】

    对于 30% 的数据,n ≤ 20。

    对于 60% 的数据,n ≤ 1000。

    对于 100% 的数据,1 ≤ n ≤ 10^5,0 ≤ m,xi ≤ 10^18,0 ≤ ti ≤ 10^9。

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