核心思路

贪心匹配 + 线段树维护可行性

问题转化

• 将水表按单价 $c_i$ 排序，单价低的水表优先分配较小读数
• 每月读数排序后，按非递减规则匹配给水表
• 最终费用 = $\sum c_i \times (\text{最终读数} - s_i)$

关键公式

1. 费用计算

总费用公式：

$$\text{总费用} = \sum_{i=1}^n c_i \times (f_i - s_i)$$

其中 $f_i$ 是第 $i$ 个水表的最终读数。

2. 单调性约束

对于任意水表 $i$，满足：

$$s_i \leq x_{i,1} \leq x_{i,2} \leq \cdots \leq x_{i,m} = f_i $$

其中 $x_{i,j}$ 是第 $j$ 个月分配给水表 $i$ 的读数。

3. 贪心匹配原则

• 单价 $c_i$ 小的水表优先分配较小的读数
• 每月将排序后的读数按顺序匹配给排序后的水表
• 用线段树维护"剩余可分配读数"的可行性

算法流程

1. 初始化：水表按 $c_i$ 排序，计算初始费用 $-\sum c_i s_i$
2. 逐月处理：
   • 当月读数排序
   • 用线段树检查并执行最优匹配
   • 若无法满足单调性则输出 NIE
3. 最终计算：加上 $\sum c_i f_i$ 得到总费用