被卡精度求助
  • 板块CF626G Raffles
  • 楼主tongyf
  • 当前回复2
  • 已保存回复2
  • 发布时间2020/12/28 21:03
  • 上次更新2023/11/5 05:33:35
查看原帖
被卡精度求助
247540
tongyf楼主2020/12/28 21:03

RT,哪里写的丑了导致精度损失了?尝试过开long double,但是开了之后从test #1 就开始错。

code:

#include<bits/stdc++.h>
#define IT set<node>::iterator
using namespace std;
const double eps=1e-10,inf=1e18;
int n,t,q,p[200005],l[200005],r[200005];
double ans=0;
int read(){
    int f=0,w=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-') w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){f=f*10+ch-'0';ch=getchar();}
    return f*w;
}
struct node{
    double val;int pos;
    bool operator < (const node &a) const{
        return val>a.val;
    }
};
multiset<node> s,e;
double calc(int x,int pos){
    if(x==-1) return inf;
    if(x>=l[pos]) return 0;
    return 1.0*p[pos]*l[pos]/(double)(x+l[pos])/(double)(x+1+l[pos]);
}
double calc1(int pos){
    return 1.0*p[pos]*(double)min(r[pos],l[pos])/(double)(min(r[pos],l[pos])+l[pos]);
}
void add(){
    IT it=e.begin();
    ans+=(*it).val;
    s.erase((node){calc(r[(*it).pos]-1,(*it).pos),(*it).pos}),s.insert(*it);
    e.erase(it),e.insert((node){calc(++r[(*it).pos],(*it).pos),(*it).pos});
}
void del(){
    IT it=s.end();it--;
    ans-=(*it).val;
    e.erase((node){calc(r[(*it).pos],(*it).pos)}),e.insert(*it);
    s.erase(it),s.insert((node){calc((--r[(*it).pos])-1,(*it).pos),(*it).pos});
}
bool check(){
    IT it1=s.end(),it2=e.begin();
    it1--;
    if((*it1).val+eps<(*it2).val) return 1;
    return 0;
}
int main(){
    n=read(),t=read(),q=read();
    for(int i=1;i<=n;i++) p[i]=read();
    for(int i=1;i<=n;i++) l[i]=read();
    for(int i=1;i<=n;i++){
        s.insert((node){inf,i});
        e.insert((node){calc(0,i),i});
    }
    while(t--) add();
    for(int i=1;i<=q;i++){
        int opt=read(),pos=read();
        s.erase((node){calc(r[pos]-1,pos),pos});e.erase((node){calc(r[pos],pos),pos}),ans-=calc1(pos);
        if(opt==1) l[pos]++;
        else if(opt==2) l[pos]--;
        s.insert((node){calc(r[pos]-1,pos),pos});e.insert((node){calc(r[pos],pos),pos}),ans+=calc1(pos);
        while((*(--s.end())).val+eps<(*(e.begin())).val) del(),add();
        printf("%.9lf\n",ans);
    }
    return 0;
}
2020/12/28 21:03
加载中...