貨幣兌換
問題描述
小 Y 最近在一家金券交易所工作。該金券交易所只發(fā)行交易兩種金券：A 紀(jì)
念券（以下簡(jiǎn)稱 A 券）和 B 紀(jì)念券（以下簡(jiǎn)稱 B 券）。每個(gè)持有金券的顧客都有
一個(gè)自己的帳戶。金券的數(shù)目可以是一個(gè)實(shí)數(shù)。
每天隨著市場(chǎng)的起伏波動(dòng)，兩種金券都有自己當(dāng)時(shí)的價(jià)值，即每一單位金券
當(dāng)天可以兌換的人民幣數(shù)目。我們記錄第 K 天中 A 券和 B 券的價(jià)值分別為 AK 和
BK （元/單位金券）。
為了方便顧客，金券交易所提供了一種非常方便的交易方式：比例交易法。
比例交易法分為兩個(gè)方面：
a) 賣出金券：顧客提供一個(gè)[0，100]內(nèi)的實(shí)數(shù)OP作為賣出比例，其意
義為：將OP%的A券和OP%的B券以當(dāng)時(shí)的價(jià)值兌換為人民幣；
b) 買入金券：顧客支付IP元人民幣，交易所將會(huì)兌換給用戶總價(jià)值為
IP的金券，并且，滿足提供給顧客的A券和B券的比例在第K天恰好為RateK；
例如，假定接下來3天內(nèi)的Ak 、Bk、Ratek 的變化分別為：
時(shí)間 Ak Bk Ratek
第一天 1 1 1
第二天 1 2 2
第三天 2 2 3
假定在第一天時(shí)，用戶手中有100元人民幣但是沒有任何金券。
用戶可以執(zhí)行以下的操作：
時(shí)間 用戶操作 人民幣(元) A券的數(shù)量 B券的數(shù)量
開戶 無 100 0 0
第一天 買入100元 0 50 50
第二天 賣出50% 75 25 25
第二天 買入60元 15 55 40
第三天 賣出100% 205 0 0
注意到，同一天內(nèi)可以進(jìn)行多次操作。
小 Y 是一個(gè)很有經(jīng)濟(jì)頭腦的員工，通過較長(zhǎng)時(shí)間的運(yùn)作和行情測(cè)算，他已經(jīng)
知道了未來 N 天內(nèi)的 A 券和 B 券的價(jià)值以及 Rate。他還希望能夠計(jì)算出來，如
果開始時(shí)擁有S元錢，那么N天后最多能夠獲得多少元錢。
輸入文件
第一行兩個(gè)正整數(shù)N、S，分別表示小Y能預(yù)知的天數(shù)以及初始時(shí)擁有的錢數(shù)。
接下來N行，第K行三個(gè)實(shí)數(shù)Ak、Bk、Ratek，意義如題目中所述。
輸出文件
只有一個(gè)實(shí)數(shù) MaxProfit，表示第 N 天的操作結(jié)束時(shí)能夠獲得的最大的金錢
數(shù)目。答案保留3位小數(shù)。
輸入樣例
3 100
1 1 1
1 2 2
2 2 3
輸出樣例
225.000
樣例說明
時(shí)間 用戶操作 人民幣(元) A券的數(shù)量 B券的數(shù)量
開戶 無 100 0 0
第一天 買入100元 0 50 50
第二天 賣出100% 150 0 0
第二天 買入150元 0 75 37.5
第三天 賣出100% 225 0 0
評(píng)分方法
本題沒有部分分，你的程序的輸出只有和標(biāo)準(zhǔn)答案相差不超過0.001時(shí)，才能
獲得該測(cè)試點(diǎn)的滿分，否則不得分。
數(shù)據(jù)規(guī)模和約定
測(cè)試數(shù)據(jù)設(shè)計(jì)使得精度誤差不會(huì)超過1e-7。
對(duì)于40%的測(cè)試數(shù)據(jù)，滿足N ≤ 10；
對(duì)于60%的測(cè)試數(shù)據(jù)，滿足N ≤ 1 000；
對(duì)于100%的測(cè)試數(shù)據(jù)，滿足N ≤ 100 000；
對(duì)于100%的測(cè)試數(shù)據(jù)，滿足：
0 < Ak ≤ 10
0 < Bk≤ 10
0 < Ratek ≤ 100
MaxProfit ≤ 1e9
提示
輸入文件可能很大，請(qǐng)采用快速的讀入方式。
必然存在一種最優(yōu)的買賣方案滿足：
每次買進(jìn)操作使用完所有的人民幣；
每次賣出操作賣出所有的金券。
===================================================================
首先有一個(gè)簡(jiǎn)單的動(dòng)態(tài)規(guī)劃：
f[i]代表第i天所能得到的最大價(jià)值，則：
f[i] = max{f[i - 1], value(j, i) = (在第j天買光f[j]的錢,在第i天賣完所得的價(jià)值)}
在第j天賣光可以得到股票B的數(shù)量 nb = f[j] / (A[j] * Rate[j] + B[j])
在第j天賣光可以得到股票A的數(shù)量 na = nb * Rate[j]
所以value(j, i) = na * A[i] + nb * B[i];
復(fù)雜度O(n^2)，60分。代碼長(zhǎng)度 < 1kb
===================================================================
但為了拿后面的40分，就變的很復(fù)雜了。。代碼長(zhǎng)度到了7~8kb。。。
把na和nb看做平面坐標(biāo)系上的點(diǎn) X[j], Y[j]
設(shè) P[j] = X[j] * A[i] + Y[j] * B[i]
移項(xiàng)有 Y[j] = (-A[i]/B[i]) X[j] + (P[j] / B[i])
所以當(dāng)P[j]達(dá)到最大的時(shí)候，也就是上面的這個(gè)一次函數(shù)截距最大的時(shí)候。
觀察可以發(fā)現(xiàn)，可以成為最大值的點(diǎn)一定是所有點(diǎn)在一象限以x遞增，y遞減的一些點(diǎn)構(gòu)成的凸殼
取得最大時(shí)：
所以我們要維護(hù)這個(gè)凸殼上的點(diǎn)。
插入時(shí)的維護(hù)：
對(duì)一條斜率已知的直線查詢時(shí)：
因?yàn)橥箽ど闲甭蔬f減，所以可以通過對(duì)某個(gè)點(diǎn)與左右的點(diǎn)所構(gòu)成直線的斜率進(jìn)行判斷：
具體維護(hù)的時(shí)候?yàn)榱诉_(dá)到較好的復(fù)雜度，要用平衡樹維護(hù)。我選擇了Splay，因?yàn)橛行┎僮髟赟play上面要方便些。。
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#define MAXN 100000
#define MIN(a,b) ((a) < (b) ? (a) : (b))
#define MAX(a,b) ((a) > (b) ? (a) : (b))
#define INFINITE 1e10
#define EPS 1e-8
using namespace std;
int n;
double f[MAXN + 1];
double A[MAXN + 1], B[MAXN + 1], Rate[MAXN + 1];
double X[MAXN + 1], Y[MAXN + 1];
void Init()
{
scanf("%d%lf", &n, &f[1]);
for (int i = 1; i <= n; i ++)
scanf("%lf%lf%lf", &A[i], &B[i], &Rate[i]);
}
class SplayNode
{
public:
int lt, rt, fa;
double x, y;
};
SplayNode node[MAXN + 1];
int cntNode = 0;
double CrossProduct(double x0, double y0, double x1, double y1, double x2, double y2)
{
return (x1 - x0) * (y2 - y0) - (y1 - y0) * (x2 - x0);
}
double CrossProduct(int a, int b, int c)
{
return CrossProduct(node[a].x, node[a].y,
node[b].x, node[b].y,
node[c].x, node[c].y);
}
class SplayTree
{
private:
int root;
void RightRotate(int x)
{
int lc = node[x].lt, fa = node[x].fa;
node[x].lt = node[lc].rt; node[node[x].lt].fa = x;
node[lc].rt = x, node[x].fa = lc;
if (fa)
{
if (x == node[fa].lt)
node[fa].lt = lc;
else
node[fa].rt = lc;
}
node[lc].fa = fa;
}
void LeftRotate(int x)
{
int rc = node[x].rt, fa = node[x].fa;
node[x].rt = node[rc].lt; node[node[x].rt].fa = x;
node[rc].lt = x, node[x].fa = rc;
if (fa)
{
if (x == node[fa].lt)
node[fa].lt = rc;
else
node[fa].rt = rc;
}
node[rc].fa = fa;
}
void Splay(int x, int FA)
{
int fa, Fa;
while (node[x].fa != FA)
{
fa = node[x].fa;
Fa = node[fa].fa;
if (Fa == FA)
{
if (x == node[fa].lt)
RightRotate(fa);
else
LeftRotate(fa);
}
else
{
if (x == node[fa].lt)
{
if (fa == node[Fa].lt)
{
RightRotate(Fa);
RightRotate(fa);
}
else
{
RightRotate(fa);
LeftRotate(Fa);
}
}
else
{
if (fa == node[Fa].rt)
{
LeftRotate(Fa);
LeftRotate(fa);
}
else
{
LeftRotate(fa);
RightRotate(Fa);
}
}
}
}
if (FA == 0)
root = x;
}
int Pred(int x)
{
if (node[x].lt)
{
x = node[x].lt;
while (true)
{
if (!node[x].rt)
return x;
x = node[x].rt;
}
}
else
{
while (true)
{
if (node[x].fa)
{
if (x == node[node[x].fa].rt)
return node[x].fa;
x = node[x].fa;
}
else
{
return 0;
}
}
}
}
int Succ(int x)
{
if (node[x].rt)
{
x = node[x].rt;
while (true)
{
if (!node[x].lt)
return x;
x = node[x].lt;
}
}
else
{
while (true)
{
if (node[x].fa)
{
if (x == node[node[x].fa].lt)
return node[x].fa;
x = node[x].fa;
}
else
{
return 0;
}
}
}
}
void Del(int now)
{
Splay(now, 0);
int pred = Pred(now), succ = Succ(now);
if (pred && succ)
{
Splay(pred, 0);
Splay(succ, root);
node[node[root].rt].lt = 0;
}
else if (pred && !succ)
{
Splay(pred, 0);
node[root].rt = 0;
}
else if (succ && !pred)
{
Splay(succ, 0);
node[root].lt = 0;
}
else
root = 0;
}
void AdjustLeft(int now)
{
while (true)
{
int p1 = Pred(now), p2 = Pred(p1);
if (p1 && p2)
{
if (CrossProduct(p2, p1, now) >= 0 || node[p1].y <= node[now].y)
Del(p1);
else
break;
}
else if (p1 && node[p1].y <= node[now].y)
{
Del(p1);
}
else
break;
}
}
void AdjustRight(int now)
{
while (true)
{
int p1 = Succ(now), p2 = Succ(p1);
if (p1 && p2)
{
if (CrossProduct(now, p1, p2) >= 0)
Del(p1);
else
break;
}
else
break;
}
}
void Adjust(int now)
{
int pred = Pred(now), succ = Succ(now);
if (pred && succ && CrossProduct(pred, now, succ) >= 0)
Del(now);
else if (succ && node[succ].y >= node[now].y)
Del(now);
else
{
AdjustLeft(now);
AdjustRight(now);
}
}
public:
SplayTree():root(0){}
void Add(double x, double y)
{
int now = root, fa = 0, flag = 0;
while (true)
{
if (!now)
{
now = ++cntNode;
node[now].x = x, node[now].y = y;
node[now].fa = fa;
if (flag == 0)
node[fa].lt = now;
else
node[fa].rt = now;
Splay(now, 0);
break;
}
else
{
fa = now;
if (x <= node[now].x) now = node[now].lt, flag = 0;
else now = node[now].rt, flag = 1;
}
}
Adjust(root);
}
double Calculate(double x, double y, double A, double factor)
{
// y = -(A / factor)x + P / factor
// P = y * factor + A * x
return A * x + y *factor;
}
double Slope(double x, double y)
{
if (fabs(x) < EPS)
return INFINITE;
return y / x;
}
double Ask(double A, double factor)
{
double k = -A / factor;
int now = root, lc, rt;
double x, y;
while (true)
{
double x = node[now].x, y = node[now].y;
int pred = Pred(now), succ = Succ(now);
if (!pred && !succ)
return Calculate(x, y, A, factor);
else if (pred && !succ)
{
if (k <= Slope(x - node[pred].x, y - node[pred].y))
return Calculate(x, y, A, factor);
else
{
if (node[now].lt)
now = node[now].lt;
else
return Calculate(x, y, A, factor);
}
}
else if (!pred && succ)
{
if (k >= Slope(node[succ].x - x, node[succ].y - y))
return Calculate(x, y, A, factor);
else
{
if (node[now].rt)
now = node[now].rt;
else
return Calculate(x, y, A, factor);
}
}
else
{
double kl = Slope(x - node[pred].x, y - node[pred].y);
double kr = Slope(node[succ].x - x, node[succ].y - y);
if (kl >= k && k >= kr)
return Calculate(x, y, A, factor);
else if (k <= kr)
now = node[now].rt;
else
now = node[now].lt;
}
}
}
};
SplayTree T;
int s[MAXN + 1];
void Solve()
{
double minx = INFINITE, maxx = -INFINITE;
/*
* P = X[j] * A[i] + Y[j] * B[i]
* Y[j] = (-A[i] / B[i]) X[j] + P / B[i];
*/
Y[1] = f[1] / (A[1] * Rate[1] + B[1]);
X[1] = Y[1] * Rate[1];
T.Add(X[1], Y[1]);
for (int j = 2; j <= n; j ++)
{
f[j] = f[j - 1];
double v = T.Ask(A[j], B[j]);
f[j] = max(f[j], v);
Y[j] = f[j] / (A[j] * Rate[j] + B[j]);
X[j] = Y[j] * Rate[j];
T.Add(X[j], Y[j]);
}
printf("%.3lf\n", f[n]);
}
int main()
{
freopen("cash.in", "r", stdin);
freopen("cash.out", "w", stdout);
Init();
Solve();
return 0;
}