P1798 小明搬家_NOI导刊2010提高(05)

    • 172通过
    • 445提交
  • 题目提供者
  • 评测方式 云端评测
  • 标签 NOI导刊 高性能
  • 难度 普及/提高-
  • 时空限制 1000ms / 128MB

题解

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

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    小明要搬家了,大家都来帮忙。

    小明现在住在第N楼,总共K个人要把X个大箱子搬上N楼。

    最开始X个箱子都在1楼,但是经过一段混乱的搬运已经乱掉了。最后大家发现这样混乱地搬运过程效率太低了,于是总结出了提高效率的方法。

    大家的速度都是每分钟上(或下)一层楼。所有向上走的人手中都拿一个箱子,所有向下走的人手中都不拿箱子。到达第N层立刻放下箱子向下走,到达第1层立刻拿起箱子向上走。当一个人向上走,另一人向下走而在楼道里相遇时,向上走的人将手中的箱子交给另一人,两人同时反向。即原来拿箱子向上走的人不拿箱子向下走,原来不拿箱子向下走的人现拿着箱子向上走。

    求将所有箱子搬完所需的最短时间。

    输入输出格式

    输入格式:

    第一行N(N≤10^9),K(K≤500000),M(M≤10^9),分别表示楼层数、人数、还放在一楼地上的箱子数。

    接下来K行,每行两个数Ai,Bi。

    Ai表示第i人现所在的楼层数,Bi为0或1,为0表示第i人正拿着箱子向上走,为1表示第i人不拿箱子向下走。

    输入满足没有任意两人正在同一楼层,在第1层的人一定正拿着箱子向上走,在第N层的人一定正不拿箱子向下走。

    输出格式:

    仅包含一个整数,为搬完箱子的时间。

    输入输出样例

    输入样例#1: 复制
    5 2 4
    1 0
    3 0
    
    输出样例#1: 复制
    20

    说明

    对于30%的数据有K≤100,M≤100;

    对于60%的数据有K≤1000,M≤l09;

    对于l000/o的数据有K≤500000,M≤109。

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