一道不难想但是很恶心的二分答案题
提前%dalao
这个题在跟庆神的激烈讨论中逐渐成熟，感谢庆神大晚上跟我思考那么久
题目截图
题目描述
给定了n个NPC,每一个NPC有两个任务,任务有两个属性,时间和收益. pavel随机等可能性地遇见其中的一个NPC,在给的两个任务中完成一个,在完成后不休止继续重复上面的过程. 求在无限长时间里的单位时间收益最大值.
题目分析和解决
这题目看上去是需要用一些概率相关的知识,但是其实跟概率论没有多大的关系.
看懂题面之后的首要任务是看懂样例, 在截图中的样例里,并不是单纯的选择每一个NPC的收益速率高的任务. 因为如果选择(1,10)和(10,20), 在等可能完成两个任务时,单位时间收益的期望是
1
2
∗
10
+
1
2
∗
20
1
2
∗
1
+
1
2
∗
10
=
5
2
<
6.4545
=
71
11
\frac{\frac{1}{2} * 10 + \frac{1}{2}*20}{\frac{1}{2} * 1 + \frac{1}{2}*10} = \frac{5}{2} < 6.4545 = \frac{71}{11}
21∗1+21∗1021∗10+21∗20=25<6.4545=1171
样例中的答案是选择了(10,70)和(1,1)的任务才得到的,这是因为想要通过选择(1,10)的任务,在11分钟里达到至少跟(10,70)一样的收益,至少需要在11次选择NPC里见到7次NPC1,这个概率是
∑
i
=
7
11
C
11
i
(
1
2
)
i
(
1
2
)
11
−
i
=
562
2048
<
0.5
\sum_{i = 7}^{11}{C^i_{11}(\frac{1}{2})^{i} (\frac{1}{2})^{11-i}} = \frac{562}{2048}<0.5
i=7∑11C11i(21)i(21)11−i=2048562<0.5 所以不如直接选择(10,70)收益更高
通过上面的分析我们也可以看到，代表概率论部分的 1/2 部分全部都可以被约掉，所以题目就转变为 求 ( ∑ 选 择 的 方 案 的 钱 数 ∑ 选 择 的 方 案 的 时 间 ) 的 最 大 值 g 求(\frac{\sum{选择的方案的钱数}}{\sum{选择的方案的时间}})的最大值g 求(∑选择的方案的时间∑选择的方案的钱数)的最大值g
同时也不难知道,g必定至少为全选ab方案的结果，同时不可能超过所有单个NPC任务中的收益效率最大值，由此我们可以确定二分答案的上下界。
判断二分答案是否合法的部分是我与庆神研究时间最长的部分。
最开始我们提出想要判断一个当前的答案curV是否合法，只需要看选择的方案能不能组合出更大的速率，那么只需要判断对于当前的NPC，假设其他NPC的方案得到的效率就是curV， 而通过选择当前NPC的任务能不能让效率增加。
就是假设
c
u
r
V
=
p
q
,
p
,
q
∈
Z
curV = \frac{p}{q},p,q\in Z
curV=qp,p,q∈Z
那么只需要不断地选择
p
+
g
o
l
d
q
+
t
i
m
e
>
p
q
\frac{p+gold}{q+time}>\frac{p}{q}
q+timep+gold>qp的方案就可以了
也就是说只要在每个方案中都选择
p
+
b
i
q
+
a
i
和
p
+
d
i
q
+
c
i
\frac{p+b_i}{q+a_i} 和 \frac{p+d_i}{q+c_i}
q+aip+bi和q+cip+di中较大的方案，就能让组合出来的速率保持在比curV更大或更接近的数值上，那么判断这个数值是否>=curV即可。
但是这样的话对需要判断的不等式进行化简
p
+
b
i
q
+
a
i
>
p
+
d
i
q
+
c
i
\frac{p+b_i}{q+a_i} > \frac{p+d_i}{q+c_i}
q+aip+bi>q+cip+di
p
(
c
i
−
a
i
)
+
q
(
b
i
−
d
i
)
+
b
i
c
i
−
d
i
a
i
>
0
p(c_i - a_i) + q(b_i - d_i) + b_ic_i - d_ia_i>0
p(ci−ai)+q(bi−di)+bici−diai>0
c
u
r
V
(
c
i
−
a
i
)
+
(
b
i
−
d
i
)
+
b
i
c
i
−
d
i
a
i
q
>
0
curV(c_i - a_i) + (b_i - d_i) + \frac{b_ic_i - d_ia_i}{q}>0
curV(ci−ai)+(bi−di)+qbici−diai>0尽管前面部分可以算出，后面避免不了需要求q，而后面的部分不能保证选择当满足上面的大于的式子的时候恒正(例如p=q=1,a=1,b=10,c=10,d=70)，所以无法省略，不可以放缩成
c
u
r
V
(
c
i
−
a
i
)
+
(
b
i
−
d
i
)
>
0
curV(c_i - a_i) + (b_i - d_i)>0
curV(ci−ai)+(bi−di)>0
此路失败
所以我们更换思路，要让
∑
1
n
g
o
l
d
i
∑
1
n
t
i
m
e
i
>
c
u
r
V
\frac{\sum_{1}^{n}gold_i}{\sum_{1}^{n}time_i} >curV
∑1ntimei∑1ngoldi>curV
只需要
∑
1
n
g
o
l
d
i
>
c
u
r
V
∑
1
n
t
i
m
e
i
\sum_{1}^{n}gold_i>curV\sum_{1}^{n}time_i
1∑ngoldi>curV1∑ntimei
也就是
∑
1
n
(
g
o
l
d
i
−
c
u
r
V
∗
t
i
m
e
i
)
>
0
\sum_{1}^{n}(gold_i - curV*time_i)>0
1∑n(goldi−curV∗timei)>0
那么对于每一个NPC，选择
(
g
o
l
d
i
−
c
u
r
V
∗
t
i
m
e
i
)
(gold_i - curV*time_i)
(goldi−curV∗timei)更大的方案无疑是相对curV来说更优秀的。所以判断函数就可喜可贺的完成了。
完成了判断函数这个题就啥都完事了
。。。。。。。。
当然不是
如果完全按照上面的思路写，得到的结果是当然不排除我二分写得不好的可能性
我们再来算一笔账
想要达到1e-9的精度最多需要二分多少次
假设下界为0，上界为1e18
那么
1
e
18
2
x
<
1
e
−
9
\frac{1e18}{2^x}<1e-9
2x1e18<1e−9
1
e
27
<
2
x
1e27<2^x
1e27<2x
27
l
o
g
2
10
<
x
27log_210<x
27log210<x
27
l
o
g
2
10
<
x
27log_210<x
27log210<x
89.692
<
x
89.692<x
89.692<x
就是最多二分不到100次，就能达到精度要求
保险起见，我们把它乘7 （只要不TLE就往死里算） 限制循环最多700次，可以通过本题
AC代码
贴上我无比丑陋的代码供大家喷
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
const int MAXX = 2e5+100;
const double ESP = 1e-10;
const int timeLimit = 700;
long long a[MAXX] , b[MAXX] , c[MAXX] , d[MAXX];
bool Check(double curV, int n)
{
double ans = 0;
for (int i = 1;i <= n;++i)
ans += max(b[i] - curV * a[i], d[i] - curV * c[i]);
return ans >= 0;
}
int main()
{
int n;
scanf("%d" , &n);
double rightLimit = 0;
long long betterTime , betterCoin;
for (int i = 1;i <= n;++i){
scanf("%lld%lld%lld%lld",&a[i],&b[i],&c[i],&d[i]);
betterTime += a[i];
betterCoin += b[i];
rightLimit = max(rightLimit , max(1.0 * b[i] / a[i], 1.0 * d[i] / c[i]));
}
double leftLimit = 1.0 * betterCoin / betterTime;
int cnt = 0;
while (rightLimit - leftLimit > ESP && cnt < timeLimit){
double mid = (rightLimit + leftLimit) / 2;
cnt++;
if (Check(mid,n))
leftLimit = mid + ESP;
else
rightLimit = mid;
}
printf("%.15lf",rightLimit);
return 0;
}