P14093 [ICPC 2023 Seoul R] Product Delivery

有一条铁路线路连接了沿海发展的 $n+1$ 个城市。当沿海城市按顺序编号为 $0$ 到 $n$ 时，城市 $(i-1)$ 和城市 $i$（$1\le i\le n$）之间通过铁路相连，其他城市之间没有铁路连接。 由于除了城市 $0$ 以外的每个城市都是著名的旅游胜地，因此每个除了城市 $0$ 以外的城市 $i$（$1\le i\le n$）正在为迎接旅游旺季准备各种商品。全球知名商品 BFB 是每个城市最受欢迎的物品。然而，该产品的供应商位于城市 $0$。 每个城市 $i$（$1\le i\le n$）只有一家出售 BFB 的店铺。记 $S_i$ 为城市 $i$ 的 BFB 专卖店。在每个 $S_i$ 中，预计在旅游季节售出的 BFB 数量都会进行分析，并以 $[l_i,m_i]$ 的形式向供应商报告。这里，$l_i$ 和 $m_i$ 分别表示预计所需产品数量的最小值和最大值。 城市 $0$ 的 BFB 供应公司会从每个城市的店铺收集需求信息，并按照以下规则进行供货： - 选择一个城市，例如城市 $k$（$1\le k\le n$）。然后，从城市 $0$ 出发，乘火车前往城市 $k$，并只向沿途的城市供货。也就是说，供应商只会向 $S_1,S_2,\dots,S_k$ 供货。 - 在沿途向每个 $S_i$（$1\le i\le k$）供应 BFB，设供应数量为 $c_i$，则需满足 $c_i\le c_{i+1}$（$1\le i\le k-1$）。 如果供应商按照如上供货规则供货，可能无法通过一次供货就满足所有店铺的需求。因此，供应商必须进行多次供货，但每次都必须遵守上述规则。所有供货操作完成后，每个 $S_i$ 的库存需不少于 $l_i$ 且不多于 $m_i$。 例如，假设 $n=4$，每家店铺 $S_i$（$1\le i\le 4$）的需求数量区间分别为 $[13,15], [5,8], [6,14], [3,7]$。要使每家店铺都获得所需数量的商品，至少需要两次供货。在第一次供货中，可以为这 $4$ 家店各送 $6$ 件。完成后，所有店除了 $S_1$ 都已满足要求。由于 $S_1$ 已经收到 $6$ 件，第二次供货时还需再送 $r$ 件（$7\le r\le 9$）。当然，也可能有其他供货方法。但无论如何，至少需要两次供货。 请编写程序，计算按照以上规则满足所有需求所需的最少供货次数。

你的程序应从标准输入读取数据。输入的第一行为一个整数 $n$（$1\le n\le 10^6$），表示有 BFB 专卖店的城市个数。接下来的 $n$ 行中，第 $i$ 行包含两个整数 $l_i$ 和 $m_i$（$1\le l_i\le m_i\le 10^9$），分别表示 $S_i$ 预计所需产品的最小值和最大值。

你的程序应向标准输出输出一行。该行应包含一个整数，表示按照供货规则满足所有需求所需的最少供货次数。

由 ChatGPT 5 翻译