题目大意
凡和邻家男孩玩完了纸牌，兴致很高，于是准备了一场表演艺术对抗赛。他特意请来了很多表演艺术家，分成绿黑两队，进行名为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;
}
|
