@codeforces - 1209H@ Moving Walkways

怼烎@ 2023-06-01 14:56 21阅读 0赞

*  @description@
 *  @solution@
 *  @accepted code@
 *  @details@

--------------------

## @description@ ##

机场中常常见到滑行道：假如一个滑行道的运行速度为 s，你的行走速度为 v，则你的真实速度为 s + v。

Limak 在数轴上走，想要从 0 走到 L。  
数轴上有 n 个不相交的滑行道（但是可以端点重叠），第 i 个滑行道占用区间 \[xi, yi\]，且它的运行速度为 si。

Limak 想要恰当地分配他的能量：他的初始能量为 0，且在任意时刻必须为非负数。  
每个时刻 Limak 都可以随意调整他的速度 v，但必须在 \[0, 2\] 中。  
每单位时间内他将失去 v 的能量，但同时会恢复 1 的能量。即他将获得 (1-v) 的能量。

求到达 L 的最短时间。

**Input**  
第一行两个整数 n, L (1≤n≤200000, 1≤L≤10^9)，含义如上。  
接下来 n 行，每行包含整数 xi, yi 以及实数 si (0≤xi<yi≤L, 0.1≤si≤10.0)。  
保证 y\[i\] <= x\[i+1\]，对于 1 <= i < n。  
**Output**  
输出一个实数，表示最短时间。

**Examples**  
**input**  
1 5  
0 2 2.0  
**output**  
3.000000000000

**input**  
1 5  
2 4 0.91  
**output**  
3.808900523560

## @solution@ ##

一个敏锐的选手应该感觉得到，这个能量 e 的定义与位移 x 大同小异：  
能量 e 定义每单位时间增加 (1-v)，位移 x 定义为每单位时间增加 v，则 e + x 每单位时间增加 1。  
于是得到某段时间内 e + x = t，所以 v 这个量就没什么价值了。但是要保证 0 <= x <= 2\*t（对应速度 v 的取值区间在 \[0, 2\] 中这一限制）。

将没有滑行道的地方看作运行速度为 0 的滑行道。  
考虑某一个滑行道，其长度为 l，运行速度为 s。则令完全地通过这个滑行道耗费时间为 t，有 l = s\*t + x = s\*t + (t - e) = (s + 1)\*t - e。  
这样一来，对于某一个滑行道，实际上只有两个量是不确定的：时间 t 与对应时间内的能量变化量 e。

我们对于每个滑行道，建立以 e 为自变量，t 为因变量的函数关系，即：  
\\\[t = \\frac\{l + e\}\{s + 1\}\\\]

尝试取出这个函数的定义域。根据 0 <= x <= 2\*t 得到 0 <= t - e <= 2\*t，再代入 t = (l + e) / (s + 1) 就可以得到 e 的范围（过程省略）：  
\\\[-\\frac\{l\}\{s + 2\}\\le e \\le \\frac\{l\}\{s\}\\\]

需要注意 s 可以取 0，这时候 e 的上界为正无穷。

我们的问题转变为，求一个数列 e\[1\], e\[2\], ...，使得 ei 在一个给定的范围内，且这个数列的任意前缀和为非负整数（这个数列表示每一个滑行道的能量变化值），而 f1(e\[1\]) + f2(e\[2\]) + ... 最大。

观察上面我们的 e-t 函数，它是一次函数且单增，即 e 增大则 t 增大。  
注意到这个问题其实很像括号匹配问题。假如 e\[i\] 减小，则必须要有一个 e\[j\]（j < i）要增大，且变化量相同。  
如果 fi(e\[i\]) 的斜率 ≥ fj(e\[j\]) 的斜率，则这个方法是一定优秀的；否则是一定不优秀的。

于是我们就可以设计一个贪心算法：将所有函数按斜率从大到小排序，对于当前函数 fi，从 i 之前取走尽量多的能量贡献给 i。容易验证这个算法的正确性。  
具体实现，可以先将 e\[i\] 设置为其上界，维护其前缀和。然后如果扫描到某个 e\[x\]，尝试将 e\[x\] 取到最小值，同时保证前缀和非负。  
这个线段树随便搞搞。

因为 s = 0 时，e 无上界。代码实现时有些小 trick。  
总时间复杂度为 O(nlogn)。

## @accepted code@ ##

#include<cstdio> #include<algorithm> using namespace std; typedef double db; const int MAXN = 200000; const db EPS = 1E-7; const db INF = 1E10; struct segtree{ #define lch (x<<1) #define rch (x<<1|1) struct node{ int l, r; db tg, mn; }t[8*MAXN + 5]; void build(int x, int l, int r) { t[x].l = l, t[x].r = r, t[x].mn = 0; if( l == r ) return ; int mid = (l + r) >> 1; build(lch, l, mid), build(rch, mid + 1, r); } void pushup(int x) { t[x].mn = min(t[lch].mn, t[rch].mn); } void pushdown(int x) { if( t[x].tg ) { t[lch].tg += t[x].tg, t[rch].tg += t[x].tg; t[lch].mn += t[x].tg, t[rch].mn += t[x].tg; t[x].tg = 0; } } void modify(int x, int l, int r, db k) { if( l > t[x].r || r < t[x].l ) return ; if( l <= t[x].l && t[x].r <= r ) { t[x].tg += k, t[x].mn += k; return ; } pushdown(x); modify(lch, l, r, k); modify(rch, l, r, k); pushup(x); } db query(int x, int l, int r) { if( l > t[x].r || r < t[x].l ) return INF; if( l <= t[x].l && t[x].r <= r ) return t[x].mn; pushdown(x); return min(query(lch, l, r), query(rch, l, r)); } }T; struct node{ db v0, s; int id; friend bool operator < (node a, node b) { return a.v0 < b.v0; } }a[2*MAXN + 5]; db e[2*MAXN + 5]; int n, L; int main() { scanf("%d%d", &n, &L); int lst = 0, cnt = 0; for(int i=1;i<=n;i++) { int x, y; db s; scanf("%d%d%lf", &x, &y, &s); cnt++, a[cnt].id = cnt, a[cnt].v0 = 0, a[cnt].s = x - lst; lst = y; cnt++, a[cnt].id = cnt, a[cnt].v0 = s, a[cnt].s = y - x; } cnt++, a[cnt].id = cnt, a[cnt].v0 = 0, a[cnt].s = L - lst; sort(a + 1, a + cnt + 1); T.build(1, 1, cnt); for(int i=1;i<=cnt;i++) if( a[i].v0 ) T.modify(1, a[i].id, cnt, e[i] = a[i].s/a[i].v0); else e[i] = 0; for(int i=1;i<=cnt;i++) { // printf("%lf %lf %lf\n", e[i], a[i].s, a[i].v0); } for(int i=1;i<=cnt;i++) { db x = e[i] - (-a[i].s/(a[i].v0 + 2)), y = T.query(1, a[i].id, cnt), z = min(x, y); // printf("%d %lf %lf\n", i, x, y); T.modify(1, a[i].id, cnt, -z), e[i] -= z; } db ans = 0; for(int i=1;i<=cnt;i++) { ans += (e[i] + a[i].s) / (a[i].v0 + 1); // printf("%d : %lf %lf %lf\n", a[i].id, e[i], a[i].s, a[i].v0); } printf("%.10lf\n", ans); }

## @details@ ##

虽然题目只给了 n 个滑行道，但滑行道之间那些“运行速度为 0 的滑行道”也有 n + 1 个，所以总共 2\*n 个滑行道。因此线段树要开到 8\*MAXN。  
因为这种很 sb 的原因 RE 了一次。。。

转载于:https://www.cnblogs.com/Tiw-Air-OAO/p/11565155.html