stdKonjac's Blog

 要做到不可替代,就要与众不同。

【卡片游戏】

题目描述

小D举办了元旦联欢活动,其中有一个卡片游戏。
游戏的规则是这样的:有 n 张卡片,每张卡片上正面写着一个小于等于 100 的正整数 ai,反面都是一样的花色。这 n 张卡片正面朝下叠成一堆,玩这个游戏的人从中可以抽出连续的 k (1≤k≤n)张卡片。如果对于这k张卡片上的数字的平均值 a,满足 l<=a<=r,那他就可以获得小礼物一件。
小W来玩这个游戏了,她事先通过某些途径知道了这 n 张卡片上写的数字,现在她想知道她获得小礼物的期望值。
小W对小数很头疼,所以请你用分数的形式告诉她答案。

输入格式

输入第 1 行,三个整数 n,l,r 。
输入第 2 行,包含 n 个整数 ai

输出格式

输出仅 1 行,表示小W获得小礼物的期望值。输出格式为“P/Q”(P 和 Q 互质)。
如果期望值是 0 或 1 就不用输出分数了。

样例数据 1

输入

4 2 3
3 1 2 4输出
7/10

样例数据 2

输入

4 1 4
3 1 2 4

输出

1

备注

【样例1解释】

《【卡片游戏】》

由表可得,一共有 10 种情况,其中有 7 种情况小W可以获得小礼物。因此小W获得小礼物的期望值是 7/10。

【样例2解释】
由上表得,小W总是可以获得小礼物。因此期望值是 1 。

【数据范围】
对于 30% 的数据,0<n≤10,000;
对于 70% 的数据,0<n≤100,000;
对于 100% 的数据,0<n≤500,000,0<l<r≤100。

直接暴力计算只能过30%……,这道题居然是求逆序对,醉了醉了,我们用sum[i]来计算到i件物品的总价值,设选j+1~i件物品是合法的(0<=j<i<=N)那么不难得出这样一个式子:l<=(sum[i]-sum[j])/(i-j) 化简得li-lj<=sum[i]-sum[j],两边移项得li-sum[i]<=lj-sum[j](j<i),同理可计算出r的式子,要满足这样的条件就直接求有几对这样的逆序对即可,注意归并排序的时候范围一定要定为(0,n),不然第一张卡片会被选漏!另外搞了1天半总算把萎靡的树状数组+离散搞出来了!范围的取舍太关键了,而且n不是500010ll的话小数据会出错!没错500010ll最后两个是字母ll不是11……(貌似是#define ll long long的效果?)真是啥也不想吐槽了……

下面是归并排序解法:


下面是树状数组+离散化解法:
点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注

*

This site uses Akismet to reduce spam. Learn how your comment data is processed.