【Codeforces 8VC Venture Cup 2016 - Elimination Round】G Raffles
Zarxdy34
posted @ 2016年3月02日 18:15
in Codeforces
with tags
线段树
, 548 阅读
随便来个数据结构维护一下就好了...不知道为什么把它放在G题。
根据官方题解里的说法，除了第一次分配，其他时刻James最多移动一张彩票的位置。（好像挺显然的？）
保险起见还是写了移动多个的。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 | #include <cmath>#include <cstdio>#include <cstring>#include <algorithm>using namespace std;const int maxn=200010;const double eps=1e-8;int p[maxn];int l[maxn];double inc[maxn],dec[maxn];int num[maxn];int n,tickets,q;double ans;double Calc(int x,int pnum) {return (double)p[x]*pnum/(l[x]+pnum);}double Changev(int x,int v) {if (num[x]+v>l[x]) return 0;if (num[x]+v<0) return 1e10;return fabs(Calc(x,num[x])-Calc(x,num[x]+v));}struct Segment_Tree{ int incmax[maxn<<2],decmin[maxn<<2]; int ID[maxn]; #define ls (o<<1) #define rs (o<<1|1) #define fa (o>>1) #define mid ((l+r)>>1) void Update(int o) { incmax[o]=(inc[incmax[ls]]>inc[incmax[rs]])?incmax[ls]:incmax[rs]; decmin[o]=(dec[decmin[ls]]<dec[decmin[rs]])?decmin[ls]:decmin[rs]; } void Build_Tree(int o,int l,int r) { if (l==r) {incmax[o]=decmin[o]=l;ID[l]=o;return;} Build_Tree(ls,l,mid); Build_Tree(rs,mid+1,r); Update(o); } int Inc_Max() {return incmax[1];} int Dec_Min() {return decmin[1];} void Change(int x,int v,int ctr) { int o=ID[x]; ans-=Calc(x,num[x]); if (ctr==0) l[x]+=v;else num[x]+=v; ans+=Calc(x,num[x]); inc[x]=Changev(x,1);dec[x]=Changev(x,-1); while (o) Update(o>>=1); }}T;int main(){ scanf("%d%d%d",&n,&tickets,&q); for (int i=1;i<=n;i++) scanf("%d",&p[i]); for (int i=1;i<=n;i++) scanf("%d",&l[i]); for (int i=1;i<=n;i++) inc[i]=Changev(i,1),dec[i]=Changev(i,-1); T.Build_Tree(1,1,n); while (tickets) { int incp=T.Inc_Max(); if (fabs(inc[incp])<eps) break; T.Change(incp,1,1); tickets--; } for (int i=1;i<=q;i++) { int t,r; scanf("%d%d",&t,&r); if (t==1) T.Change(r,1,0);else T.Change(r,-1,0); if (num[r]>l[r]) T.Change(r,-1,1),tickets++; int incp=T.Inc_Max(),decp=T.Dec_Min(); while (tickets && fabs(inc[incp])>eps) { T.Change(incp,1,1); tickets--; incp=T.Inc_Max(); } while (inc[incp]>dec[decp]) { T.Change(incp,1,1); T.Change(decp,-1,1); incp=T.Inc_Max(),decp=T.Dec_Min(); } printf("%f\n",ans); } return 0;} |
我上面的代码里打的是线段树，然而其实只要两个堆就够了。
评论 (0)
