Codeforces 626G Raffles 【贪心】【线段树】

题意：

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

每个奖池的奖金为pi。

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

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

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

保证：

n,t,q<=2e5

ai<=1000 pi<=1000

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

思路：

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

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

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

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

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

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

线段树几天没写手有点生...

#include<bits/stdc++.h>
using namespace std;
double power[200050];
int num[200050];
int have[200050];
struct tr{
    int get_id,lose_id,s,e;
    double ans,get,lose;
    void updatte(){
        ans=power[s]*min(1.0*have[s]/(have[s]+num[s]),0.5);
        get_id=lose_id=s;
        if(have[s]>=num[s])get=0;
        else{
            get=power[s]*(have[s]+1)/(have[s]+num[s]+1);
            get-=power[s]*have[s]/(have[s]+num[s]);
        }
        if(have[s]>num[s])lose=0;
        else if(have[s]){
            lose=power[s]*have[s]/(have[s]+num[s]);
            lose-=power[s]*(have[s]-1)/(have[s]+num[s]-1);
        }
        else lose=1e18;
    }
};
tr tree[200050<<2];
void update(int k){
    tree[k].ans=tree[k<<1].ans+tree[k<<1|1].ans;
    tree[k].get=max(tree[k<<1].get,tree[k<<1|1].get);
    tree[k].lose=min(tree[k<<1].lose,tree[k<<1|1].lose);
         if(tree[k<<1].get<tree[k<<1|1].get)tree[k].get_id=tree[k<<1|1].get_id;
    else tree[k].get_id=tree[k<<1].get_id;
    if(tree[k<<1].lose<tree[k<<1|1].lose)tree[k].lose_id=tree[k<<1].lose_id;
    else tree[k].lose_id=tree[k<<1|1].lose_id;
}
void build(int s,int e,int k){
    tree[k].s=s;
    tree[k].e=e;
    if(s==e){
        tree[k].updatte();
        return;
    }
    int mid=(s+e)>>1;
    build(s,mid,k<<1);
    build(mid+1,e,k<<1|1);
    update(k);
}
int ttmp=0;
void nnn(int pos,int k){
    int s=tree[k].s;
    int e=tree[k].e;
    if(s==e){
        tree[k].updatte();
        return;
    }
    int mid=(s+e)>>1;
    if(pos<=mid)nnn(pos,k<<1);
    else nnn(pos,k<<1|1);
    update(k);
}
int main()
{
    int n,t,q;
    scanf("%d%d%d",&n,&t,&q);
    for(int i=1;i<=n;i++){
        scanf("%lf",&power[i]);
    }
    for(int i=1;i<=n;i++){
        scanf("%d",&num[i]);
    }
    build(1,n,1);
    while(t>0){
        int get_id=tree[1].get_id;
        have[get_id]++;
        nnn(get_id,1);
        t--;
    }
    for(int i=0;i<q;i++){
        int typ,id;
        scanf("%d%d",&typ,&id);
        if(typ==1){
            num[id]++;
            nnn(id,1);
            while(tree[1].get>tree[1].lose){
                int get_id=tree[1].get_id;
                int lose_id=tree[1].lose_id;
                have[get_id]++;
                have[lose_id]--;
                nnn(get_id,1);
                nnn(lose_id,1);
            }
        }
        else{
            num[id]--;
            nnn(id,1);
            while(tree[1].get>tree[1].lose){
                int get_id=tree[1].get_id;
                int lose_id=tree[1].lose_id;
                have[get_id]++;
                have[lose_id]--;
                nnn(get_id,1);
                nnn(lose_id,1);
            }
        }
        printf("%.12lf\n",tree[1].ans);
    }
    return 0;
}

Codeforces 626G Raffles 【贪心】【线段树】

推荐阅读