P16598 [SYSUCPC 2025] Network

计算机网络是计算机科学中一门非常重要的课程。假设有两台机器 A 与 B，它们需要通过一条由 $n-1$ 台路由器构成的链式网络进行数据传输。 具体而言，当机器 A 希望向机器 B 发送数据时，它首先将数据发送至路由器 1，路由器 1 再转发至路由器 2，路由器 2 转发至路由器 3，如此继续，直至路由器 $n-1$ 最终将数据转发至机器 B。 现在，机器 A 需要向机器 B 发送 $K$ 比特的数据。它首先将数据划分为 $m$ 个分组，每个分组的大小为 $l_i$，满足 $\sum l_i=K$。这些分组按照 $l_1,l_2,\dots,l_m$ 的顺序依次推入路由器 1。机器 A 的推送速率为 $r_0$ bit/s，路由器 1 的推送速率为 $r_1$ bit/s，……，路由器 $n-1$ 的推送速率为 $r_{n-1}$ bit/s。 路由器以分组为单位进行转发。当一个路由器接收到某一分组的若干比特后，它会等待该分组的全部比特均已到达，才开始将该分组推送给下一台路由器。路由器的转发策略为先到先服务。当某台路由器正在转发来自一个分组的数据时，来自其他分组的数据将被暂存在该路由器的缓存中等待转发。 假设机器或路由器一旦推送某个比特，该比特会立即到达下一台路由器或机器。问题是：从机器 A 推送第一个比特的时刻开始计算，机器 B 将在什么时刻完整接收到机器 A 所发送的全部 $K$ 比特数据？

第一行包含三个正整数 $n$（$1 \leq n \leq 10^5$）、$m$（$1 \leq m \leq 3\times 10^5$）、$K$（$1\leq K\leq 3\times 10^5$），分别表示机器 A 与机器 B 之间经过 $n-1$ 台路由器进行通信，机器 A 将要传送给 B 的数据分为 $m$ 个分组，以及机器 A 希望传送给 B 的总数据比特数为 $K$。 第二行包含 $n$ 个正整数。第一个整数为 $r_0$（$1\leq r_0\leq 10^9$），表示机器 A 的推送速率（单位为 bit/s）。随后的 $n-1$ 个整数为 $r_i$（$1\leq r_i\leq 10^9$），其中第 $i$ 个整数表示第 $i$ 台路由器的推送速率（单位为 bit/s）。 第三行包含 $m$ 个正整数。第 $i$ 个整数为 $l_i$（$1\leq l_i\leq K$），表示第 $i$ 个分组所含的比特数。数据保证 $\sum l_i=K$。

输出一个实数，以秒为单位，表示从机器 A 推送第一个比特开始，到机器 B 完整接收机器 A 希望传送给 B 的全部 $K$ 比特数据所经过的时间。假设你的答案为 $Your\_Answer$，标准答案为 $Answer$。如果满足 $\frac{|Your\_Answer-Answer|}{Answer}\leq 10^{-9}$ 或 $|Your\_Answer-Answer|\leq 10^{-9}$，则你的答案将被视为正确。

数据链路为：A $\to$ 路由器 1 $\to$ B，其中 A 的推送速率为 2 bit/s，路由器 1 的推送速率为 1 bit/s。 A 打算向 B 传送 3 比特数据。发送前，A 将数据划分为两个分组，长度分别为 1 比特和 2 比特。A 先推送长度为 1 的分组，随后推送长度为 2 的分组。 第二个分组在等待 $\frac{1+2}{2}=1.5$ 秒后完全推入路由器 1。由于第一个分组在等待 $\frac{1}{2}=0.5$ 秒后（即 A 推送该分组所用的时间）完全到达路由器 1，而路由器 1 完整接收第一个分组后需花费 $\frac{1}{1}=1$ 秒将其完全推送出去，第二个分组恰好在第一个分组被路由器 1 完全推送完毕时到达路由器 1。因此第二个分组无需在路由器 1 排队，可以立即被推送出去。故而答案为 $\frac{2+1}{2}+\frac{2}{1}=3.5$ 秒。 翻译由 DeepSeek V3.2 完成