P6351: [ZJOI2010]贪吃的老鼠
特殊裁判/
SPJ
1.000s
时间限制
128MB
内存限制
1 提交
0 解决
【题目描述】
奶酪店里最近出现了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。