[Codeforces626G] Raffles

做法

猜了个结论,不会证但是又想不到其他做法..看了眼题解发现是对的。

对于第 \(i\) 个抽奖,假设你买了 \(x\) 次,你从这个抽奖中获得的钱数的期望是 \(p_i\frac {x} {x + l_i}\)。假设你已经买了第 \(i\) 个抽奖 \(x\) 次,再买一次,期望的增加量是 \(p_i(\frac{x+1}{x+l_i+1} - \frac{x}{x+l_i}) = p_i \frac{l_i}{(x+l_i)(x+l_i+1)}\)。容易发现这个增加量关于 \(x\) 单调递减,所以我们只要对于所有的 \(i\)\(x \le i\),把 \(p_i \frac{l_i}{(x+l_i)(x+l_i+1)}\) 丢进一个数组,从大到小排个序,前 \(t\) 个数之和即是答案。但是这样做复杂度不能接受。

我们先算出初始清空的最优方案,给第 \(k\) 个抽奖原有的票数加一减一之后,考虑两种操作:一,少买一个抽奖 \(k\),多买一个另一个抽奖;二,多买一个抽奖 \(k\),少买一个另一个抽奖。我们找到能使期望增加量最大的操作,这很容易用堆来维护。只需要经过一次这样的操作即可得到最优方案,证明就不具体写出了。(比如说如果是进行操作二,从进行一次操作二后,再进行一次操作二的减小量要比在修改票数之前进行一次操作二的减小量要大来考虑即可)

代码

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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
#include <bits/stdc++.h>

using namespace std;

typedef long double ld;
typedef long long ll;

const int maxn = 200010;
const ld eps = 1e-10;

ld ans = 0;

int n, t, q;
int p[maxn], l[maxn], cur[maxn];

int gcd(int x, int y) {
if (!y) return x;
return gcd(y, x%y);
}

struct frac {
ll x, y;
int i;
frac(ll x_=0, ll y_=0, int i_=0) {
x = x_, y = y_;
int d = gcd(x, y);
x /= d, y /= d;
i = i_;
}
};

bool operator<(const frac &f1, const frac &f2) {
if (1LL * f1.x * f2.y != 1LL * f1.y * f2.x) return 1LL * f1.x * f2.y < 1LL * f1.y * f2.x;
return f1.i < f2.i;
}

bool operator>(const frac &f1, const frac &f2) {
if (1LL * f1.x * f2.y != 1LL * f1.y * f2.x) return 1LL * f1.x * f2.y > 1LL * f1.y * f2.x;
return f1.i > f2.i;
}

bool operator==(const frac &f1, const frac &f2) {
return f1.x == f2.x && f1.y == f2.y && f1.i == f2.i;
}

priority_queue<frac, vector<frac>, less<frac> > pq1, d1;
priority_queue<frac, vector<frac>, greater<frac> > pq2, d2;

void upd1() {
while (!d1.empty() && d1.top() == pq1.top()) {
d1.pop();
pq1.pop();
}
}

void upd2() {
while (!d2.empty() && d2.top() == pq2.top()) {
d2.pop();
pq2.pop();
}
}

void del(int i) {
if (cur[i] < l[i]) {
d1.push(frac(p[i] * l[i], 1LL * (cur[i] + l[i]) * (cur[i] + l[i] + 1), i));
}
if (cur[i]) {
d2.push(frac(p[i] * l[i], 1LL * (cur[i] - 1 + l[i]) * (cur[i] - 1 + l[i] + 1), i));
}
}

void add(int i) {
if (cur[i] < l[i]) {
pq1.push(frac(p[i] * l[i], 1LL * (cur[i] + l[i]) * (cur[i] + l[i] + 1), i));
}
if (cur[i]) {
pq2.push(frac(p[i] * l[i], 1LL * (cur[i] - 1 + l[i]) * (cur[i] - 1 + l[i] + 1), i));
}
}

ld cal(int i) {
return ld (p[i]) * ld(cur[i]) / ld(cur[i] + l[i]);
}

void mt() {
while (t) {
upd1();
if (pq1.empty()) break;
frac f = pq1.top();
int i = f.i;
del(i);
ans -= cal(i);
// cout << i << " " << cur[i] << endl;
++ cur[i];
ans += cal(i);
add(i);
t --;
}
while (1) {
upd1(); upd2();
if (pq1.empty() || pq2.empty()) return;
frac f1 = pq1.top(), f2 = pq2.top();
if (ld (f1.x) / ld (f1.y) - ld (f2.x) / ld (f2.y) < eps) return;
del(f1.i); del(f2.i);
ans -= cal(f1.i); ans -= cal(f2.i);
++ cur[f1.i], -- cur[f2.i];
ans += cal(f1.i); ans += cal(f2.i);
add(f1.i); add(f2.i);
}
}

int main() {
scanf("%d%d%d", &n, &t, &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++) add(i);
for (int i = 1; i <= q; i++) {
int ty, r; scanf("%d%d", &ty, &r);
if (ty == 1) {
// + 1
del(r);
ans -= cal(r);
++ l[r];
ans += cal(r);
add(r);
mt();
} else {
// - 1
del(r);
ans -= cal(r);
if (cur[r] == l[r]) {
-- cur[r], ++ t;
}
-- l[r];
ans += cal(r);
add(r);
mt();
}
printf("%.10lf\n", double (ans));
}
return 0;
}