隐藏
「计蒜客16967」表演艺术 - 数学 | Bill Yang's Blog

路终会有尽头,但视野总能看到更远的地方。

0%

「计蒜客16967」表演艺术 - 数学

题目大意

    凡和邻家男孩玩完了纸牌,兴致很高,于是准备了一场表演艺术对抗赛。他特意请来了很多表演艺术家,分成绿黑两队,进行名为PK,实则捞金的表演。
    凡为了捞金,开设了一个赌局,在比赛开始之前招揽人们来押注谁能胜出,在所有人进行投注之后,凡需要告诉大家绿方和黑方的单位返还金额都是多少。
    举个例子,如果绿方的单位返还金额为$5$,那么我每押$1$块钱绿方胜,如果成真就能拿回$5$块钱,但是如果结果绿方输了,我就拿不回来任何钱。
    凡决定将单位返还金额设得更具有吸引力,所以他要求“绿方胜的单位返还金额+黑方胜的单位返还金额=$T$”,并且为了赚更多的钱,凡可以在中间某两个投注的人之间更改单位返还金额,但是要求双方的总和仍然为$T$,并且只能更改一次。
    不幸的是,凡突然发现自己请来的表演艺术家竟然和众多投注人是一伙的,也就是说,在凡定下单位返还金额之后,那些艺术家会操纵比赛结果,从而让凡拿出更多的钱来。
    这下凡有些慌了,于是他来询问你应该怎么制定单位返还金额。


题目分析

我们将每部分的和如图设为$A_1,A_2,B_1,B_2$,设赔率分别为$x_1,x_2$。

则答案为$\min(A_1\times x_1+A2\times x_2,B_1\times(T-x_1)+B_2\times(T-x_2))$。

显然,当两部分相等的时候可以使得答案最小。

则:

整理得到:

在满足上述等式时最小化目标函数$f(x)=A_1\times x_1+A_2\times x_2$。

不难发现,该函数只可能让$x_1,x_2$在极值点的时候取到,因此令$A_1,A_2$最小值最大(能取到$T$最好),最大值最小(能取到$0$最好)。


代码

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
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;

inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}

const int maxn=500005;
int n;
double T,sum1[maxn],sum2[maxn],Ans=1e18;

int main() {
ios::sync_with_stdio(false);
cin>>n;
for(int i=1; i<=n; i++) {
double x,y;
cin>>x>>y;
sum1[i]=sum1[i-1]+x;
sum2[i]=sum2[i-1]+y;
}
cin>>T;
for(int i=1; i<=n; i++) {
double A1=sum1[i],B1=sum2[i],A2=sum1[n]-A1,B2=sum2[n]-B1,x1,x2;
x1=T*(B1+B2)/(A1+B1);
if(x1>T) {
x1=T;
x2=(T*(B1+B2)-(A1+B1)*x1)/(A2+B2);
} else x2=0;
Ans=min(Ans,A1*x1+A2*x2);
x2=T*(B1+B2)/(A2+B2);
if(x2>T) {
x2=T;
x1=(T*(B1+B2)-(A2+B2)*x2)/(A1+B1);
} else x1=0;
Ans=min(Ans,A1*x1+A2*x2);
}
printf("%0.2lf\n",Ans);
return 0;
}
姥爷们赏瓶冰阔落吧~