求帮忙
查看原帖
求帮忙
234596
tangchenhui楼主2024/7/12 17:35

实在调不出了,求大佬帮忙

#include<bits/stdc++.h>
#define N 500005
#define lb long double
using namespace std;
int n,m;
lb p,ans=0;
int b[N];
lb tr[N],c[N];
int lowbit(int x){
    return x&-x;
}
lb query(int x){
    lb cnt=0;
    while (x){
        cnt+=tr[x];
        x-=lowbit(x);
    }
    return cnt;
}
void change(int x,lb v){
    while (x<n){
        tr[x]+=v;
        x+=lowbit(x);
    }
}
priority_queue<int> a[N];
int main(){
    scanf("%d%d",&n,&m);
    scanf("%Lf",&p);
    c[0]=1;
    for (int i=1;i<=n;i++)
        c[i]=c[i-1]*(1-p);
    for (int i=1;i<=m;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        a[x].push(-y);
        b[x]++;
    }
    for (int i=1;i<=n;i++){
        int j=0;
        while (a[i].size()){
            int x=-a[i].top();
            a[i].pop();
            ans+=p*c[j]*(query(n)-query(x))/(1-c[b[i]]);
            change(x,(p*c[j])/(1-c[b[i]]));
            j++;
//            printf("%d %d %Lf\n",i,x,ans);
        }
    }
    printf("%.2Lf",ans);
    return 0;
}
2024/7/12 17:35
加载中...