首页 > 代码库 > BZOJ1492: [NOI2007]货币兑换Cash
BZOJ1492: [NOI2007]货币兑换Cash
1492: [NOI2007]货币兑换Cash
Time Limit: 5 Sec Memory Limit: 64 MBSubmit: 1556 Solved: 724
[Submit][Status]
Description
小 Y 最近在一家金券交易所工作。该金券交易所只发行交易两种金券：A 纪
念券（以下简称 A 券）和 B 纪念券（以下简称 B 券）。每个持有金券的顾客都有
一个自己的帐户。金券的数目可以是一个实数。
每天随着市场的起伏波动，两种金券都有自己当时的价值，即每一单位金券
当天可以兑换的人民币数目。我们记录第 K 天中 A 券和 B 券的价值分别为 AK和
BK（元/单位金券）。
为了方便顾客，金券交易所提供了一种非常方便的交易方式：比例交易法。
比例交易法分为两个方面：
a)
卖出金券：顾客提供一个[0，100]内的实数 OP 作为卖出比例，其意
义为：将 OP%的 A 券和 OP%的 B 券以当时的价值兑换为人民币；
b)
买入金券：顾客支付 IP 元人民币，交易所将会兑换给用户总价值为
IP 的金券，并且，满足提供给顾客的 A 券和 B 券的比例在第 K 天恰好为 RateK；
Input
第一行两个正整数N、S，分别表示小Y 能预知的天数以及初始时拥有的钱数。 接下来N 行，第K 行三个实数AK、BK、RateK，意义如题目中所述
Output
只有一个实数MaxProfit，表示第N 天的操作结束时能够获得的最大的金钱 数目。答案保留3 位小数。
Sample Input
3 100
1 1 1
1 2 2
2 2 3
1 1 1
1 2 2
2 2 3
Sample Output
225.000
HINT
测试数据设计使得精度误差不会超过10-7。
对于40%的测试数据，满足N ≤ 10；
对于60%的测试数据，满足N ≤ 1 000；
对于100%的测试数据，满足N ≤ 100 000；
Source
题解：
CDQ分治说起来容易，写起来也不容易。。。
它之所以能够保持O(n*logn)的复杂度 是因为 T(n)=2*T(n/2)+O(n) 的解为 T（n）=n*logn
所以 在计算 l--mid 对 mid+1--r 的影响时所有的操作时间都必须是线性的
所以 在 合并的时候 我们要求
1.求凸包不需要排序
2.询问 k 单调，只需用单调队列
要解决第一点，我们只需要 按归并排序的思想每次递归调用结束时 merge l--r 即可
要解决第二点，我们需要预处理对k排序，使得在solve分治的时候 ，直接分到mid+1 --r的k是有序的，尽管序号可能并不是连续的，但这不影响答案
这是一个优美的算法。
代码：
1.我找的代码
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cmath> 5 #include<cstring> 6 #define maxn 120000 7 #define eps 1e-9 8 #define inf 1e9 9 using namespace std; 10 struct query 11 { 12 double q,a,b,rate,k; 13 int pos; 14 }q[maxn],nq[maxn]; 15 double fabs(double x) 16 { 17 return (x>0)?x:-x; 18 } 19 struct point 20 { 21 double x,y; 22 friend bool operator <(const point &a,const point &b) 23 { 24 return (a.x<b.x+eps)||(fabs(a.x-b.x)<=eps&&a.y<b.y+eps); 25 } 26 }p[maxn],np[maxn]; 27 int st[maxn]; 28 double f[maxn]; 29 int n,m; 30 31 double getk(int i,int j) 32 { 33 if (i==0) return -inf; 34 if (j==0) return inf; 35 if (fabs(p[i].x-p[j].x)<=eps) return -inf; 36 return (p[i].y-p[j].y)/(p[i].x-p[j].x); 37 } 38 39 void solve(int l,int r) 40 { 41 if (l==r)//此时l之前包括l的f值已经达到最优，计算出对应的点即可 42 { 43 f[l]=max(f[l-1],f[l]); 44 p[l].y=f[l]/(q[l].a*q[l].rate+q[l].b); 45 p[l].x=p[l].y*q[l].rate; 46 return ; 47 } 48 int mid=(l+r)>>1,l1=l,l2=mid+1; 49 //对询问集合排序，1位置2斜率 50 for (int i=l;i<=r;i++) 51 if (q[i].pos<=mid) nq[l1++]=q[i]; 52 else nq[l2++]=q[i]; 53 for (int i=l;i<=r;i++) q[i]=nq[i]; 54 //递归左区间 55 solve(l,mid); 56 //左半区所有点都以计算好，把它们入栈，维护凸壳 57 int top=0; 58 for (int i=l;i<=mid;i++) 59 { 60 while (top>=2&&getk(i,st[top])+eps>getk(st[top],st[top-1])) top--; 61 st[++top]=i; 62 } 63 //拿左半区更新右半区 64 int j=1; 65 for (int i=r;i>=mid+1;i--)//保证询问斜率递减 66 { 67 while (j<top&&q[i].k<getk(st[j],st[j+1])+eps) j++; 68 f[q[i].pos]=max(f[q[i].pos],p[st[j]].x*q[i].a+p[st[j]].y*q[i].b); 69 } 70 //递归右区间 71 solve(mid+1,r); 72 //合并左右区间的点，按照x,y排序 73 l1=l,l2=mid+1; 74 for (int i=l;i<=r;i++) 75 if ((p[l1]<p[l2]||l2>r)&&l1<=mid) np[i]=p[l1++]; 76 else np[i]=p[l2++]; 77 for (int i=l;i<=r;i++) p[i]=np[i]; 78 } 79 80 bool cmp(query a,query b) 81 { 82 return a.k<b.k; 83 } 84 85 int main() 86 { 87 freopen("input.txt","r",stdin); 88 freopen("output2.txt","w",stdout); 89 scanf("%d%lf",&n,&f[0]); 90 for (int i=1;i<=n;i++) 91 { 92 scanf("%lf%lf%lf",&q[i].a,&q[i].b,&q[i].rate); 93 q[i].k=-q[i].a/q[i].b; 94 q[i].pos=i; 95 } 96 sort(q+1,q+n+1,cmp); 97 solve(1,n); 98 //for(int i=1;i<=n;i++)cout<<i<<‘ ‘<<f[i]<<endl; 99 printf("%.3lf\n",f[n]);100 return 0;101 }
2.我的代码（基本一样。。。都是抄的。。。）
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cmath> 4 #include<cstring> 5 #include<algorithm> 6 #include<iostream> 7 #include<vector> 8 #include<map> 9 #include<set>10 #include<queue>11 #define inf 100000000012 #define maxn 100000+100013 #define maxm 500+10014 #define eps 1e-1015 #define ll long long16 #define pa pair<int,int>17 using namespace std;18 struct rec{double a,b,rate,k;int id;}q[maxn],nq[maxn];19 struct point20 {21 double x,y;22 friend bool operator <(const point &a,const point &b)23 {24 return (a.x<b.x+eps||(fabs(a.x-b.x)<eps&&a.y<b.y+eps));25 }26 }p[maxn],np[maxn];27 double f[maxn];28 int sta[maxn],n;29 double getk(int i,int j)30 {31 if(!i)return -inf;32 if(!j)return inf;33 if(fabs(p[i].x-p[j].x)<=eps)return -inf;34 return (p[i].y-p[j].y)/(p[i].x-p[j].x);35 }36 void solve(int l,int r)37 {38 if(l==r)39 {40 f[l]=max(f[l],f[l-1]);41 p[l].y=f[l]/(q[l].a*q[l].rate+q[l].b);42 p[l].x=p[l].y*q[l].rate;43 return;44 } 45 int mid=(l+r)>>1,l1=l,l2=mid+1;46 for(int i=l;i<=r;i++)47 if(q[i].id<=mid)nq[l1++]=q[i];else nq[l2++]=q[i];48 for(int i=l;i<=r;i++)q[i]=nq[i];49 solve(l,mid);50 int top=0;51 for(int i=l;i<=mid;i++)52 {53 while(top>=2&&getk(i,sta[top])+eps>getk(sta[top],sta[top-1]))top--;54 sta[++top]=i;55 } 56 int j=1;57 for(int i=r;i>=mid+1;i--)58 {59 while(j<top&&q[i].k<getk(sta[j],sta[j+1])+eps)j++;60 f[q[i].id]=max(f[q[i].id],p[sta[j]].x*q[i].a+p[sta[j]].y*q[i].b);61 }62 solve(mid+1,r);63 l1=l;l2=mid+1;64 for(int i=l;i<=r;i++)65 if((p[l1]<p[l2]||l2>r)&&l1<=mid)np[i]=p[l1++];else np[i]=p[l2++];66 for(int i=l;i<=r;i++)p[i]=np[i];67 }68 bool cmp(rec a,rec b)69 {70 return a.k<b.k;71 }72 int main()73 {74 freopen("input.txt","r",stdin);75 freopen("output.txt","w",stdout);76 scanf("%d%lf",&n,&f[0]);77 for(int i=1;i<=n;i++)78 {79 scanf("%lf%lf%lf",&q[i].a,&q[i].b,&q[i].rate);80 q[i].k=-q[i].a/q[i].b;81 q[i].id=i;82 }83 sort(q+1,q+n+1,cmp);84 solve(1,n);85 //for(int i=1;i<=n;i++)cout<<i<<‘ ‘<<f[i]<<endl;86 printf("%.3lf\n",f[n]);87 return 0; 88 }
BZOJ1492: [NOI2007]货币兑换Cash
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。