本题与逛超市的区别仅在于盲盒中剩下物品的要求,以及本题S的数据范围为n≤S≤109。
没想到吧,我居然在这里!
题目描述
野豌豆正在参加超市抽奖活动,抽奖活动共有n个奖项,奖池中第i个奖项总共有ai份,如果抽中第i个奖项将会获得一份价值为wi的奖品。抽奖方式为从盲盒里抽签,初始时盲盒中总共有m=∑i=1nai份签,其中表示第i个奖项的签数总共有ai个。商店老板绝对公平,保证你抽到每个签的概率是相等的。
现在野豌豆仅获得了一次抽奖的机会,不过当野豌豆逛完超市来抽奖时已经来晚了,商店老板告诉你现在盲盒里剩下不超过S份签了(即剩下奖品的总数不超过S个),但好消息是每种奖项的奖品至少还剩下一份。野豌豆此时心中有种不祥的预感,于是他想问你在最坏情况下,自己抽到奖品的期望价值最小是多少。
关于期望的定义:假设抽到第i个奖项的概率为pi,那么抽奖一次获得奖品的期望价值为E=∑i=1npiwi
输入格式
第一行包含两个正整数n和S,表示总共有n(1≤n≤300000)个奖项,且余下奖品总数不超过S(n≤S≤109)个。
第i+1行包含两个正整数ai,wi,表示第i个奖项在初始时总共有ai(1≤ai≤106)份,抽中第i个奖项时会获得价值为wi(1≤wi≤109)的奖品。
输出格式
输出一个小数x,为野豌豆最坏情况下抽到奖品的期望价值,要求与答案的相对误差或绝对误差不超过10−6。
也就是说,如果你给出的答案是a,正确答案是b,你的答案被认为是正确的当且仅当max(1,b)∣a−b∣<10−6。
样例
数据范围
对于30%的数据,1≤n≤100,1≤ai≤100,n≤S≤1000。
对于100%的数据,1≤n≤3×105,1≤ai≤106,1≤wi≤109 ,n≤S≤109。
提示
对于第一组数据,可以证明当所剩奖品的价值分别是1,1,1,5,6,7,10时,野豌豆可以抽到的期望价值最小,为73×1+71×5+71×6+71×7+71×10=731
对于第二组数据,因为每种奖品都至少剩下一份,所以所剩商品的价值只能为3000,1000,64800,2,1,答案为13760.6。