比赛 |
清华集训2017模板练习 |
评测结果 |
AAAAAAAAAA |
题目名称 |
货币兑换 |
最终得分 |
100 |
用户昵称 |
lyqlyqcogs |
运行时间 |
1.056 s |
代码语言 |
C++ |
内存使用 |
5.66 MiB |
提交时间 |
2017-07-17 14:19:33 |
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<deque>
using namespace std;
const int SIZEN=100010;
int N;
double S;
double A[SIZEN]={0},B[SIZEN]={0},Rate[SIZEN]={0};
double f[SIZEN]={0},g[SIZEN]={0};
double ans=0;
int leftlis[SIZEN]={0},rightlis[SIZEN]={0};
void printcoor(int a){
printf("(%lf %lf)",f[a],g[a]);
}
bool cmp_f(int a,int b){//f[a]<f[b]?
if(f[a]==f[b]) return g[a]<g[b];
return f[a]<f[b];
}
bool cmp_pro(int a,int b){//-A[a]/B[a]>-A[b]/B[b]?
//即A[a]/B[a]<A[b]/B[b]
return A[a]*B[b]<A[b]*B[a];
}
deque<int> H;//凸线
//本题中x,y坐标分别是f,g
bool under(int a,int b,int c){//b是否在ac下方
if(f[b]==f[a]) return g[b]<=g[a];
if(f[b]==f[c]) return g[b]<=f[c];
double x1=f[a]-f[b],y1=g[a]-g[b];
double x2=f[c]-f[b],y2=g[c]-g[b];
return x1*y2-x2*y1<0;
}
void make_hull(int l,int r){//将leftlis[l~r]所含元素的凸线存在H中
//现在leftlis[l~r]已经排序,f值递增
H.clear();
for(int i=l;i<=r;i++){
while(H.size()>=2&&under(H[H.size()-2],H[H.size()-1],leftlis[i])) H.pop_back();
H.push_back(leftlis[i]);
}
}
double get_slope(int a,int b){//ab的斜率
return (g[a]-g[b])/(f[a]-f[b]);
}
double maxmoney[SIZEN]={0};
void calc(int j,int i){//用j去计算并更新i的最大金钱值
double money=f[j]*A[i]+f[j]/Rate[j]*B[i];
ans=max(ans,money);
maxmoney[i]=max(maxmoney[i],money);
}
void update(int l,int r){//用H中的决策更新rightlis[l~r],这是l~r的一个排列
for(int i=l;i<=r;i++){
double k=-A[rightlis[i]]/B[rightlis[i]];//应当把斜率不小于k的都删掉
while(H.size()>=2&&get_slope(H[0],H[1])>=k) H.pop_front();
calc(H[0],rightlis[i]);
}
for(int i=l;i<=r;i++){
maxmoney[i]=max(maxmoney[i],maxmoney[i-1]);
f[i]=max(f[i],maxmoney[i]*Rate[i]/(A[i]*Rate[i]+B[i]));
g[i]=f[i]/Rate[i];
}
}
void solve(int l,int r){
if(l==r){
ans=max(ans,f[l]);
g[l]=f[l]/Rate[l];
return;
}
int mid=(l+r)>>1;
solve(l,mid);
for(int i=l;i<=mid;i++) leftlis[i]=i;
for(int i=mid+1;i<=r;i++) rightlis[i]=i;
//左边序列按照f值递增排序,右边序列按照-a[i]/b[i]递减排序
sort(leftlis+l,leftlis+mid+1,cmp_f);
sort(rightlis+mid+1,rightlis+r+1,cmp_pro);
make_hull(l,mid);
update(mid+1,r);
solve(mid+1,r);
}
void work(void){
f[1]=S*Rate[1]/(A[1]*Rate[1]+B[1]);
g[1]=f[1]/Rate[1];
maxmoney[0]=maxmoney[1]=S;
solve(1,N);
printf("%.3lf\n",ans);
}
void read(void){
scanf("%d",&N);
scanf("%lf",&S);
ans=S;
for(int i=1;i<=N;i++) scanf("%lf%lf%lf",&A[i],&B[i],&Rate[i]);
}
int main(){
freopen("cash.in","r",stdin);
freopen("cash.out","w",stdout);
read();
work();
return 0;
}