P2570 [ZJOI2010]贪吃的老鼠

    • 109通过
    • 317提交
  • 题目提供者
  • 评测方式 云端评测
  • 标签 二分答案 网络流 2010 浙江 Special Judge
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

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

    推荐的相关题目 显示

    题目描述

    奶酪店里最近出现了m只老鼠!它们的目标就是把生产出来的所有奶酪都吃掉。奶酪店中一天会生产n块奶酪,其中第i块的大小为pi,会在第ri秒被生产出来,并且必须在第di秒之前将它吃掉。第j只老鼠吃奶酪的速度为sj,因此如果它单独吃完第i快奶酪所需的时间为pi/sj。老鼠们吃奶酪的习惯很独特,具体来说:

    (1) 在任一时刻,一只老鼠最多可以吃一块奶酪;

    (2) 在任一时刻,一块奶酪最多被一只老鼠吃。

    由于奶酪的保质期常常很短,为了将它们全部吃掉,老鼠们需要使用一种神奇的魔法来延长奶酪的保质期。将奶酪的保质期延长T秒是指所有的奶酪的di变成di+T。同时,使用魔法的代价很高,因此老鼠们希望找到最小的T使得可以吃掉所有的奶酪。

    输入输出格式

    输入格式:

    输入文件的第一行包含一个整数K,表示输入文件中数据的组数。

    每组数据的第一行包含两个整数n和m,分别表示奶酪和老鼠的数量。接下来的n行每行包含三个整数pi,ri,di。最后m行每行包含一个整数,表示sj。pi,ri,di,sj的含义如上文所述。

    输出格式:

    包含K 行,每行包含一个实数,表示你找到的最小的T。你的答案和标准答案的绝对误差不应超过10−4。

    输入输出样例

    输入样例#1: 复制
    2
    2 2
    13 0 4
    10 1 3
    4
    2
    1 1
    1 0 2
    1
    
    输出样例#1: 复制
    0.5
    0
    

    说明

    样例说明

    第一组数据中:

     第0到第1秒:第一只老鼠吃第一块奶酪;

     第1到第3.5秒:

    • 第一只老鼠吃第二块奶酪;

    • 第二只老鼠吃第一块奶酪;

     第3.5到第4.5秒:第一只老鼠吃第一块奶酪。

    数据规模

    30%的数据中,1≤n,m≤5;

    100%的数据中,1≤K≤5,1≤n,m≤30,1≤pi≤10^5, 0 ≤ri<di≤10^7,1≤sj≤10^5。

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