2017-04-09

【bzoj1492】货币兑换

本文为博主原创，未经许可不得转载

AC通道

建议阅读CDQ的论文《从Cash谈一类分治算法的应用》：传送门

这东西还挺好写的

注意：在计算左边对右边贡献时，必须保证左边是按f排序，右边是按k排序，由于f是现求的，所以在分治前必须先按k排序，归并时按f排序

#include<bits/stdc++.h>
#define FILE "read"
#define MAXN (int)1e5+10
#define eps 1e-8
#define cmin(a,b) a=min(a,b)
#define cmax(a,b) a=max(a,b)
using namespace std;
struct node{
	double a,b,rate,x,y,k;  int id;
	bool operator < (const node z)const {return k>z.k;}
}p[MAXN],sta[MAXN];
int n,st[MAXN];
double f[MAXN];
inline int read(){
	int x=0,f=1;  char ch=getchar();
	while(!isdigit(ch))  {if(ch=='-')  f=-1;  ch=getchar();}
	while(isdigit(ch))  {x=x*10+ch-'0';  ch=getchar();}
	return x*f;
}
double slop(int a,int b){
	if(!b)return -1e20;
	if(fabs(p[a].x-p[b].x)<eps)return 1e20;
	return (p[b].y-p[a].y)/(p[b].x-p[a].x);
}
void solve(int l,int r){
	if(l==r){
		cmax(f[l],f[l-1]);
		p[l].x=f[l]*p[l].rate/(p[l].a*p[l].rate+p[l].b);
		p[l].y=p[l].x/p[l].rate;
		return;
	}
	int mid=(l+r)>>1,ta=l,tb=mid+1,top=0,j=1;
	for(int i=l;i<=r;++i){
		if(p[i].id<=mid)  sta[ta++]=p[i];
		else sta[tb++]=p[i];
	}
	for(int i=l;i<=r;++i)  p[i]=sta[i];
	solve(l,mid);
	for(int i=l;i<=mid;++i){
		while(top>1&&slop(i,st[top])+eps>slop(st[top],st[top-1]))  --top;
		st[++top]=i;
	}st[++top]=0;
	for(int i=mid+1;i<=r;++i){
		while(j<top&&slop(st[j],st[j+1])+eps>p[i].k) ++j;
		cmax(f[p[i].id],p[st[j]].x*p[i].a+p[st[j]].y*p[i].b);
	}
	solve(mid+1,r);  ta=l;  tb=mid+1;
	for(int i=l;i<=r;++i){
		if((p[ta].x<p[tb].x||(abs(p[ta].x-p[tb].x)<eps)&&p[ta].y<p[tb].y||tb>r)&&ta<=mid) sta[i]=p[ta++];
		else sta[i]=p[tb++];
	}
	for(int i=l;i<=r;++i)  p[i]=sta[i];
}
int main(){
	freopen(FILE".in","r",stdin);
	freopen(FILE".out","w",stdout);
	n=read();  f[0]=read();
	for(int i=1;i<=n;++i){
		scanf("%lf%lf%lf",&p[i].a,&p[i].b,&p[i].rate);
		p[i].id=i;  p[i].k=-p[i].a/p[i].b;
	}
	sort(p+1,p+n+1);
	solve(1,n);
	printf("%.3lf\n",f[n]);
	return 0;
}

本文标题:【bzoj1492】货币兑换

文章作者:chty

发布时间:2017年04月09日 - 19时47分

最后更新:2018年03月02日 - 17时31分

许可协议:本文为博主原创，未经许可不得转载。