95 计费法是华为云在许多场景下的网络带宽计费方法,即某个节点的费用通过一个计费周期内所有网络流量采样点的 95 分位点来计算。当拥有很多个可进行流量调度的节点时,问题就变得有趣起来了。作为降低成本的重要一环,华为云需要你聪明的脑袋使用各种奇技淫巧来把这个计费点摁下去。
但是对于小 A 来说并没有这个烦恼。小 A 只有一个可用节点,所有的流量都只能往上堆。虽然小 A 没有钱,但是他拥有重新划分计费区间的神奇能力。小 A 需要你的帮助。对于一个有 $n$ 个网络采样点的时间区间,小 A 希望你将这个区间重新划分为 $m$ 个非空区间,并最小化每段的分位点之和。
简短题意:
给一个长度为 $n$ 的序列 $a[1..n]$,将其分为 $m$ 段(不可为空),使得每段的 95 分位点大小之和最小。
95 分位点:区间第 $len-\lfloor 0.05 \times len \rfloor$ 小的数,$len$ 表示区间长度(元素个数)。