Codeforces 626G Raffles(贪心+线段树)

简介: G. Raffles time limit per test:5 seconds memory limit per test:256 megabytes input:standard input output:standard output Johnny is at a carnival which has n raffles.

G. Raffles

time limit per test:5 seconds
memory limit per test:256 megabytes
input:standard input
output:standard output

Johnny is at a carnival which has n raffles. Raffle i has a prize with value pi. Each participant can put tickets in whichever raffles they choose (they may have more than one ticket in a single raffle). At the end of the carnival, one ticket is selected at random from each raffle, and the owner of the ticket wins the associated prize. A single person can win multiple prizes from different raffles.

However, county rules prevent any one participant from owning more than half the tickets in a single raffle, i.e. putting more tickets in the raffle than all the other participants combined. To help combat this (and possibly win some prizes), the organizers started by placing a single ticket in each raffle, which they will never remove.

Johnny bought t tickets and is wondering where to place them. Currently, there are a total of li tickets in the i-th raffle. He watches as other participants place tickets and modify their decisions and, at every moment in time, wants to know how much he can possibly earn. Find the maximum possible expected value of Johnny's winnings at each moment if he distributes his tickets optimally. Johnny may redistribute all of his tickets arbitrarily between each update, but he may not place more than t tickets total or have more tickets in a single raffle than all other participants combined.

Input

The first line contains two integers n, t, and q (1 ≤ n, t, q ≤ 200 000) — the number of raffles, the number of tickets Johnny has, and the total number of updates, respectively.

The second line contains n space-separated integers pi (1 ≤ pi ≤ 1000) — the value of the i-th prize.

The third line contains n space-separated integers li (1 ≤ li ≤ 1000) — the number of tickets initially in the i-th raffle.

The last q lines contain the descriptions of the updates. Each description contains two integers tk, rk (1 ≤ tk ≤ 2, 1 ≤ rk ≤ n) — the type of the update and the raffle number. An update of type 1 represents another participant adding a ticket to raffle rk. An update of type 2 represents another participant removing a ticket from raffle rk.

It is guaranteed that, after each update, each raffle has at least 1 ticket (not including Johnny's) in it.

Output

Print q lines, each containing a single real number — the maximum expected value of Johnny's winnings after the k-th update. Your answer will be considered correct if its absolute or relative error does not exceed 10 - 6.

Namely: let's assume that your answer is a, and the answer of the jury is b. The checker program will consider your answer correct, if .

Examples
Input
2 1 3
4 5
1 2
1 1
1 2
2 1
Output
1.666666667
1.333333333
2.000000000
Input
3 20 5
6 8 10
6 6 6
1 1
1 2
1 3
2 3
2 3
Output
12.000000000
12.000000000
11.769230769
12.000000000
12.000000000
Note

In the first case, Johnny only has one ticket to distribute. The prizes are worth 4 and 5, and the raffles initially have 1 and 2 tickets, respectively. After the first update, each raffle has 2 tickets, so Johnny has expected value of winning by placing his ticket into the second raffle. The second update adds a ticket to the second raffle, so Johnny can win in the first raffle. After the final update, Johnny keeps his ticket in the first raffle and wins .

In the second case, Johnny has more tickets than he is allowed to spend. In particular, after the first update, there are 7, 6, and 6 tickets in each raffle, respectively, so Johnny can only put in 19 tickets, winning each prize with probability . Also, note that after the last two updates, Johnny must remove a ticket from the last raffle in order to stay under the tickets in the third raffle.

题目链接:http://codeforces.com/contest/626/problem/G

题意:

给n个奖池,t张彩票,q次操作。

每个奖池的奖金为pi。

每个奖池现有的彩票的数量为ai,保证ai>=1;

q次操作,每次有两种,第i个奖池的现有彩票数量加一,或减一。

不允许投票的数量多于奖池数量的二分之一。

保证:

n,t,q<=2e5

ai<=1000 pi<=1000

求在采用最佳策略的前提下获得奖金的期望。

思路:

首先要证明贪心的正确性,即把某张票投入某奖池之后其下一张票给期望做出的贡献要小于上一张彩票...

把式子写一下,求导,发现导数是单调递减的...

然后是对于每次操作的处理。

一开始一直纠结如何处理从某奖池拿出的亏损。因为按照贡献差来说第一个和后来的是有区别的,而且还要处理是否超票的问题。 

但是看了卿学姐的思路...

其实思路是很简洁的,大概的内容是维护一个亏损的线段树一个盈利的线段树,亏损的意思是从某一奖池拿出一张票我们期望的减少,盈利的意思是往某一奖池投入一张票期望的增加。其实奖池的投递数量不用限制的,只要把盈利控制为0就可以了。而对于减少某奖池现有彩票的数量,直接对上限和投递数量的数组进行处理,然后更新维护这个奖池的盈利和亏损就可以了。因为亏损和盈利是可以直接根据这两个数据确定的。

下面给出AC代码:【卿学姐的代码,参考一下,待补】

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 const int maxn = 2e5+6;
  4 inline int read()
  5 {
  6     int x=0,f=1;char ch=getchar();
  7     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
  8     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
  9     return x*f;
 10 }
 11 int x[maxn],y[maxn],p[maxn];
 12 struct treenode
 13 {
 14   int L , R  ;
 15   double Up,Down,Max,Min,ans;
 16   void updata()
 17   {
 18         ans=1.0*p[L]*min(1.0*x[L]/(x[L]+y[L]),0.5);
 19       if(x[L]>=y[L])Up=0;
 20       else
 21       {
 22           Up=1.0*p[L]*(x[L]+1.0)/(x[L]+y[L]+1.0);
 23           Up-=1.0*p[L]*x[L]/(x[L]+y[L]);
 24       }
 25       if(x[L])
 26       {
 27           if(x[L]>y[L])Down=0;
 28           else
 29           {
 30               Down=1.0*p[L]*x[L]/(x[L]+y[L]);
 31               Down-=1.0*p[L]*(x[L]-1.0)/(x[L]-1.0+y[L]);
 32           }
 33       }
 34       else
 35         Down=1e18;
 36   }
 37 };
 38 treenode tree[maxn*4];
 39 inline void push_up(int o)
 40 {
 41     tree[o].ans=tree[o<<1].ans+tree[o<<1|1].ans;
 42     tree[o].Up=max(tree[o<<1].Up,tree[o<<1|1].Up);
 43     tree[o].Down=min(tree[o<<1].Down,tree[o<<1|1].Down);
 44     if(tree[o<<1].Up>tree[o<<1|1].Up)
 45         tree[o].Max=tree[o<<1].Max;
 46     else
 47         tree[o].Max=tree[o<<1|1].Max;
 48     if(tree[o<<1].Down<tree[o<<1|1].Down)
 49         tree[o].Min=tree[o<<1].Min;
 50     else
 51         tree[o].Min=tree[o<<1|1].Min;
 52 }
 53 
 54 inline void build_tree(int L , int R , int o)
 55 {
 56     tree[o].L = L , tree[o].R = R, tree[o].ans=0;
 57     if(L==R)
 58         tree[o].Min=tree[o].Max=L,tree[o].updata();
 59     if (R > L)
 60     {
 61         int mid = (L+R) >> 1;
 62         build_tree(L,mid,o*2);
 63         build_tree(mid+1,R,o*2+1);
 64         push_up(o);
 65     }
 66 }
 67 
 68 inline void updata(int QL,int o)
 69 {
 70     int L = tree[o].L , R = tree[o].R;
 71     if (L==R)
 72     {
 73         tree[o].updata();
 74     }
 75     else
 76     {
 77         int mid = (L+R)>>1;
 78         if (QL <= mid) updata(QL,o*2);
 79         else updata(QL,o*2+1);
 80         push_up(o);
 81     }
 82 }
 83 int main()
 84 {
 85     int n,t,q,mx,mi;
 86     scanf("%d%d%d",&n,&t,&q);
 87     for(int i=1;i<=n;i++)
 88         p[i]=read();
 89     for(int i=1;i<=n;i++)
 90         y[i]=read();
 91     build_tree(1,n,1);
 92     while(t--)mx=tree[1].Max,x[mx]++,updata(mx,1);
 93     while(q--)
 94     {
 95         int type,r;type=read(),r=read();
 96         if(type==1)y[r]++;else y[r]--;
 97         updata(r,1);
 98         while(1)
 99         {
100             int mx = tree[1].Max;
101             int mi = tree[1].Min;
102             if(tree[1].Up<=tree[1].Down)break;
103             x[mx]++,x[mi]--;
104             updata(mx,1);
105             updata(mi,1);
106         }
107         printf("%.12f\n",tree[1].ans);
108     }
109 }

 

目录
相关文章
codeforces 272C. Dima and Staircase(线段树)
题目很长,看加猜加谷歌翻译才看懂了题目。每级台阶的宽都是1,但高不同,并且告诉你了,然后给你m个箱子,长和宽都告诉你,把箱子靠左放,求箱子的底部有多高。
31 0
|
机器学习/深度学习 算法
蓝桥杯:递推算法 递归算法 例题:斐波纳契数列
蓝桥杯:递推算法 递归算法 例题:斐波纳契数列
71 0
|
存储 算法
【回溯算法篇】组合问题(上)
【回溯算法篇】组合问题(上)
【回溯算法篇】组合问题(上)
|
人工智能 算法 搜索推荐
LeetCode 周赛 338,贪心 / 埃氏筛 / 欧氏线性筛 / 前缀和 / 二分查找 / 拓扑排序
大家好,我是小彭。 上周末是 LeetCode 第 338 场周赛,你参加了吗?这场周赛覆盖的知识点很多,第四题称得上是近期几场周赛的天花板。
116 0
【回溯算法篇】组合问题(下)
【回溯算法篇】组合问题(下)
【回溯算法篇】组合问题(下)
|
算法
算法竞赛百日——快速排序 - 分治
算法竞赛百日——快速排序 - 分治
算法竞赛百日——快速排序 - 分治
|
C++
这道「岛屿题」用并查集做就体现出其威力了!
之前的岛屿题,用 DFS 和 BFS 来做要比用并查集更加好做并且高效,但是最对这一道题来说,用并查集要更加好做。
106 0
|
安全 算法 存储
算法导论——最小生成树
  对于一个连通图来说,我们可以去掉其中一些边依然保持其连通的性质,在这些图中存在一个或多个图,他们的路径总和是最小的,这样的图必然是树。因为,如果说图中存在环,则去掉环的一条边依然可以保证连通性,这与总路径和最小是矛盾的。
1540 0