题目描述
Takuru 是一名情报强者, 所以他想利用他强大的情报搜集能力来当中间商赚差价.
Takuru 的计划是让 Hinae 帮他去市场上买一个商品, 然后再以另一个价格卖掉它. Takuru 会给 Hinae 一定的钱 p?p?.(p?p? 是一个非负的实数)
这个商品的市场价是一个在 [l, r]?[l,r]? 内均匀随机的实数.
如果 p \geqslantp? 市场价, 那么 Hinae 会买下这个商品, 然后私吞剩下的钱. 也就是说, Takuru 以 pp 的代价买来了这个商品.
如果 p <p< 市场价, 那么 Hinae 既不会买下商品, 又不会私吞任何钱. 也就是说, Takuru 的利润为 0?0?.
当 Hinae 买下了商品后, Takuru 会生成一个在 [L, R][L,R] 内均匀随机的实数 qq, 并把商品以 qq 的价格卖掉. 那么 Takuru 的利润就是 q - p?q−p?.
Takuru 想要获得最多的利润, 所以你要帮 Takuru 确定给 Hiane 的钱 pp, 使得 Takuru 的期望利润最大. 请求出最大的期望利润.
输入描述
第一行两个正整数 ll 和 rr (1\leqslant l <r \leqslant 20001?l<r?2000).
第二行两个正整数 LL 和 RR (1\leqslant L < R \leqslant 20001?L<R?2000).
输出描述
一个实数, 表示最大的期望利润.(四舍五入后保留 44 位小数, 输出超过 44 位或少于 44 位都会获得 Wrong Answer.)
如果答案为 00, 请不要输出多余的负号.
若答案为 vv, 保证 v+10^{-6}v+10−6 以及 max(v-10^{-6},0)max(v−10−6,0) 四舍五入后保留 44 位小数的结果不会改变.
样例输入 1
400 1200 600 1800
样例输出 1
200.0000
样例输入 2
1999 2000 1 2
样例输出 2
0.0000
思路:
因为主人公的售价是 L~R 所以 主人公售价的期望是 (L+R)/2
我们给买手的钱是p, 那么我们主人公的利润就是 ((L+R)/2-p)
我们知道 期望 = 值*概率
利润期望 = 利润值*概率
我们来看下概率,
P必须取到 l和r之间, 因为如果p大于r, 那么不是最优的选择, 因为可以选择r可以产生更好的利益.
而p小于l的话, 买手会无法购物商品, 所以也不可以.
那么p就在 l和r之间了,
买手能买商品的时候当且仅当 商品的市场价 恰好小于等于p, 也就是市场价y小于p时, 可以购买,
那么y的范围时 l~p, 总范围是l~r, 所以概率是 (p-l)/(r-l)
期望就是
((L+R)/2-p)*(p-l)/(r-l)
公式就是一个关于p的二次函数, 并且a是小于等于0的, 有极大值, 我们判定对称轴是否在l到r之间,
如果在, 那么函数的极值就是答案, 如果不在, 那么取区间的左右极限的较大值是答案.
注意处理以下0*负数 =-0的情况,
细节见code
- #include <iostream>
- #include <cstdio>
- #include <cstring>
- #include <algorithm>
- #include <cmath>
- #include <queue>
- #include <stack>
- #include <map>
- #include <set>
- #include <vector>
- #include <iomanip>
- #define ALL(x) (x).begin(), (x).end()
- #define rt return
- #define dll(x) scanf("%I64d",&x)
- #define xll(x) printf("%I64d\n",x)
- #define sz(a) int(a.size())
- #define all(a) a.begin(), a.end()
- #define rep(i,x,n) for(int i=x;i<n;i++)
- #define repd(i,x,n) for(int i=x;i<=n;i++)
- #define pii pair<int,int>
- #define pll pair<long long ,long long>
- #define gbtb iOS::sync_with_stdio(false),cin.tie(0),cout.tie(0)
- #define MS0(X) memset((X), 0, sizeof((X)))
- #define MSC0(X) memset((X), '\0', sizeof((X)))
- #define pb push_back
- #define mp make_pair
- #define fi first
- #define se second
- #define eps 1e-6
- #define gg(x) getInt(&x)
- #define db(x) cout<<"== ["<<x<<"] =="<<endl;
- using namespace std;
- typedef long long ll;
- ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
- ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
- ll powmod(ll a,ll b,ll MOD){ll ans=1;while(b){if(b%2)ans=ans*a%MOD;a=a*a%MOD;b/=2;}return ans;}
- inline void getInt(int* p);
- const int maxn=1000010;
- const int inf=0x3f3f3f3f;
- /*** TEMPLATE CODE * * STARTS HERE ***/
- double l,r;
- double L,R;
- int main()
- {
- //freopen("D:\\common_text\\code_stream\\in.txt","r",stdin);
- //freopen("D:\\common_text\\code_stream\\out.txt","w",stdout);
- gbtb;
- cin>>l>>r;
- cin>>L>>R;
- double t=(L+R)/2.00;
- double k=(r-l);
- double a=-1.00/k;
- double b=(t+l)/k;
- double c=-l*t/k;
- double x=-b/(2.00*a);
- double ans;
- if(x>=l&&x<=r)
- {
- ans=(4*a*c-b*b)/(4*a);
- // db(a*x*x+b*x+c);
- }else
- {
- ans=a*l*l+b*l+c;
- ans=max(ans,a*r*r+b*r+c);
- }
- ans+=eps;
- ans=max(0.0,ans-eps);
- cout<<fixed<<setprecision(4)<<ans<<endl;
- return 0;
- }
- inline void getInt(int* p) {
- char ch;
- do {
- ch = getchar();
- } while (ch == '' || ch =='\n');
- if (ch == '-') {
- *p = -(getchar() - '0');
- while ((ch = getchar())>= '0' && ch <= '9') {
- *p = *p * 10 - ch + '0';
- }
- }
- else {
- *p = ch - '0';
- while ((ch = getchar())>= '0' && ch <= '9') {
- *p = *p * 10 + ch - '0';
- }
- }
- }
来源: http://www.bubuko.com/infodetail-3059519.html