#P4030. [HEOI2015]小L的白日梦

    ID: 3231 传统题 2000ms 256MiB 尝试: 215 已通过: 48 难度: 8 上传者: 标签>CF2500提高+/省选-期望线性性排序贪心交换论证相向双指针有理数精确运算添加哨兵枚举法概率期望

[HEOI2015]小L的白日梦

题目描述

在某一天,你有了一个女性朋友。

你打算利用 kk 天时间陪她,每天有很多种娱乐方式可供选择,你需要从中选择一种进行(一天只能进行一个项目),比如说一起去看电影、一起去主题公园,一起去逛街等等,一共 nn 种项目。当然每个项目重复太多次你都会觉得无聊,因此第 ii 个项目最多进行 cic_i 次。你虽然智商很高,但是情商堪忧,即使这些你准备的活动都是希望让她开心的,不过由于你笨拙的语言表达和过于理智的行动,可能使这些活动出现意外。经过你悉心的计算,你发现如果某一天进行了第 ii 个项目,如果一切顺利的话她应该是很高兴的,但她会有 aia_i 的概率不高兴。如果她本来是很高兴的,但突然今天你让她不高兴了,她就会觉得很失落,并且对你的好感度大大下降。你希望尽可能避免这种情况发生,因此你要安排这 kk 天之内每天进行的项目,最小化她感到失落的期望次数。

你的女性朋友十分在意你,所以她的心情只会因为你发生改变。第一天之前,因为你没有邀请她进行任何活动,所以她是不高兴的。

输入格式

第一行有一个整数 tt(1≤t≤101\le t\le10),表示一共有 tt 组数据。

对于每组数据,第一行有两个正整数 n,kn,k,分别表示你准备的项目个数和你用来陪她的天数。(n≤105n\le 10^5,k≤109k\le10^9)

接下来 nn 行,每一行描述一个项目,格式为 x/y c,其中斜杠是输入的一部分,表示进行完这个项目之后她有xiyi\frac{x_i}{y_i}的概率不高兴,并且这个项目只能进行不超过 cic_i 次。(0≤xi≤yi≤1040\le x_i\le y_i\le10^4,yi≥1y_i\ge1,0≤ci≤1090\le c_i\le10^9)

输出格式

一共 tt 行,对于每组数据输出使她感到失落的最小期望次数,四舍五入保留 66 位小数。

3
1 2
0/1 3
1 2
1/1 3
1 2
1/2 3
0.000000
0.000000
0.250000

样例说明

考虑第三组数据,因为只有一个项目所以只好每天都安排这个。

在第一天之前她总是不高兴的,一共有:

第一天不高兴,第二天也不高兴、

第一天高兴,第二天不高兴、

第一天不高兴,第二天高兴、

第一天高兴,第二天也高兴,

这四种情况,又因为每天的项目让她高兴或者是不高兴的概率都是0.5,因此这四种情况是等概率发生的。

只有在第二种情况下,她会感到失落一次。

因此答案是 (1∗1+0∗3)÷4=0.25(1*1+0*3)\div 4=0.25。

数据范围

对于前 10%10\% 的数据,n,k≤5n,k\le 5。

对于前 30%30\% 的数据,n,k≤7n,k\le 7。

对于前 40%40\% 的数据,n,k≤10n,k\le 10。

对于前 60%60\% 的数据,n≤1000,k≤105n\le 1000,k\le 10^5。

对于 100%100\% 的数据,n≤105n\le 10^5,k≤109k\le 10^9,保证 ∑i=1nci≥k\sum_{i=1}^{n} c_i\ge k,可以安排满 kk 天。

题目来源