UOJ161 【清华集训2015】园子里题解

题目链接：#161. 【清华集训2015】园子里

题意：

cxy 在园子里过着快乐而充实的生活。突然有一天，从天而降 $n$ 根柱子，这 $n$ 根柱子在学堂路上排成一排，第 $i$ 根柱子高度为 $h_i$（即$h_i$ 为原始高度）米，然而，当有人站在第 $i$ 根柱子上的时候，第 $i$ 根柱子的高度会下降 $t_i$（即当有人在上面时候 $h_i-t_i$ 就是当前高度）米，离开之后又会恢复。cxy 对这些柱子非常感兴趣，他可以从一根柱子跳到任意一个（包括他原本站着的柱子）原始高度不超过他所在柱子当前高度的柱子上，如果有多个柱子都满足，他会随机等概率地跳到一个满足条件的柱子上，如果没有柱子满足，他就会跳到地上。

cxy 想知道，如果他从第 $i$ 个柱子开始，期望跳多少次可以跳到地上。

输入格式：

第一行一个整数 $n$，表示柱子的数量。

第二行 $n$ 个空格隔开的整数 $h_i$，表示每根柱子的高度（单位：米）。

第三行 $n$ 个空格隔开的整数 $t_i$，表示有人站在第 $i$ 根柱子上的时候高度会下降 $t_i$ 米。

输出格式：

输出一行 $n$ 个浮点数，每两个浮点数用一个空格隔开，第 $i$ 个数表示 cxy 从第 $i$ 根柱子开始，期望跳多少步可以跳到地上，如果期望步数为无穷，输出 $0$ ；如果你输出的每个浮点数与标准答案的误差（此处误差定义为你的答案与标准答案差的绝对值）均不超过 $0.001$ ，你的答案将被视为正确。

注意，我们会用一个特殊的程序来判断你的答案正确与否，你输出每个浮点数的字符串长度应该不超过 $20$ 。

定义无穷可以参与运算，无穷 + X = 无穷，无穷 - X = 无穷，无穷 * X = 无穷，无穷 / X = 无穷（X 为任一实数，在除法中不为 0）

数据范围：

$1 \le n \le 10^6,~1\le h_i \le 10^5,~0 \le t_i \le h_i$

注意到这个跳的过程类似于DAG，因此考虑dp

设 $f_i$ 表示从柱子 $i$ 跳回地面的期望步数。记 $h^{\prime}_i = h_i-t_i$ ，则

$f_i = 1 + \frac{\sum_{h_j \le h_i^{\prime}}f_j}{\sum_{h_j \le h_i^{\prime}} 1}$

若 $\sum_{h_j \le h_i^{\prime}} 1 = 0$ ，则定义 $f_i=1$ （直接跳地上）。

但是观察转移方程可以发现，如果 $h_i = h_i^{\prime}$ ，即自己可以跳到自己身上，就会导致循环转移。

考虑将所有 $h_i=h_i^{\prime}$ 且高度相等的所有柱子一起处理。

设有 $k$ 个「 $h_i=h_i^{\prime}$ 且高度相等」的柱子，跳回地面的期望步数为 $r$ ，则

$r = 1 +\frac{\sum_{h_j \le h_i\land h_j^{\prime} < h_i}f_j + k\times r}{\sum_{h_j \le h_i^{\prime}} 1}$

设 $A=\sum_{h_j \le h_i\land h_j^{\prime} < h_i}f_j,~B = \sum_{h_j \le h_i^{\prime}} 1$ ，解得 $r=\dfrac{A+B}{B-k}$ 。

若 $B=k$ ，则此时所有高度不超过 $h_i$ 的柱子均为 $h_i$ ，并且 $h_i = h^{\prime}_i$ ，显然有 $r=+\infty$

时间复杂度 $O(n \log n + h_{\max})$

代码：（这题有点卡常）

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
namespace FastIO
{
    #define gc() readchar()
    #define pc(a) putchar(a)
    #define SIZ (int)(1e6+15)
    char buf1[SIZ],*p1,*p2;
    char readchar()
    {
        if(p1==p2)p1=buf1,p2=buf1+fread(buf1,1,SIZ,stdin);
        return p1==p2?EOF:*p1++;
    }
    template<typename T>void read(T &k)
    {
        char ch=gc();T x=0,f=1;
        while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
        while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
        k=x*f;
    }
    template<typename T>void write(T k)
    {
        if(k<0){k=-k;pc('-');}
        static T stk[66];T top=0;
        do{stk[top++]=k%10,k/=10;}while(k);
        while(top){pc(stk[--top]+'0');}
    }
}using namespace FastIO;
#define N ((int)(1e6+15))
#define M ((int)(1e5+15))
#define F first
#define S second
int n,mx,H[N],h[N],sc[M];
double f[N],sf[M];
vector< pair<int,int> > v[M];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    // cout << fixed << setprecision(8);
    read(n);
    for(int i=1; i<=n; i++) read(H[i]);
    for(int i=1,x; i<=n; i++)
    {
        read(x); h[i] = H[i] - x;
        mx = max(mx, H[i]);
        v[H[i]].emplace_back(h[i],i);
    }
    for(int i=1; i<=mx; i++)
    {
        sc[i] = sc[i-1] + v[i].size();
        sf[i] = sf[i-1]; int x=0;
        for(auto t : v[i])
        {
            if(t.F < i)
            {
                f[t.S] = (sc[t.F] ? (sf[t.F] / (double)sc[t.F]) : 0) + 1;
                sf[i] += f[t.S];
            }else ++x;
        }
        double r = (x == sc[i] ? INFINITY : 1.0 * (sf[i] + sc[i]) / (sc[i]-x));
        for(auto t : v[i])
            if(t.F == i) sf[i] += (f[t.S] = r);
    }
    for(int i=1; i<=n; i++)
        printf("%.8lg%c",(isfinite(f[i]) ? f[i] : 0.0), " \n"[i==n]);
    return 0;
}