当前你的浏览器版本过低,网站已在兼容模式下运行,兼容模式仅提供最小功能支持,网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。

建议使用的浏览器:

谷歌Chrome 火狐Firefox Opera浏览器 微软Edge浏览器 QQ浏览器 360浏览器 傲游浏览器

7256:95计费法

题目描述
95 计费法是华为云在许多场景下的网络带宽计费方法,即某个节点的费用通过一个计费周期内所有网络流量采样点的 95 分位点来计算。当拥有很多个可进行流量调度的节点时,问题就变得有趣起来了。作为降低成本的重要一环,华为云需要你聪明的脑袋使用各种奇技淫巧来把这个计费点摁下去。

但是对于小 A 来说并没有这个烦恼。小 A 只有一个可用节点,所有的流量都只能往上堆。虽然小 A 没有钱,但是他拥有重新划分计费区间的神奇能力。小 A 需要你的帮助。对于一个有 $n$ 个网络采样点的时间区间,小 A 希望你将这个区间重新划分为 $m$ 个非空区间,并最小化每段的分位点之和。

简短题意:

给一个长度为 $n$ 的序列 $a[1..n]$,将其分为 $m$ 段(不可为空),使得每段的 95 分位点大小之和最小。

95 分位点:区间第 $len-\lfloor 0.05 \times len \rfloor$ 小的数,$len$ 表示区间长度(元素个数)。
输入解释
第一行一个整数 $T$,表示数据组数。($1 \le T \le 10$)

对于每组数据:

第一行两个整数 $n$ 和 $m$。($1 \le m \le n \le 100$)

第二行 $n$ 个整数,表示序列 $a$。($0 \le a[i] \le 1000$)
输出解释
对于每组数据,输出一个整数,表示最小的 95 分位点大小之和。
输入样例
2
5 2
777 96 114 920 206
5 5
804 253 746 267 487
输出样例
1126
2557

该题目是Virtual Judge题目,来自 杭电HDUOJ

源链接: HDU-7256

最后修改于 2022-09-15T06:17:38+00:00 由爬虫自动更新

共提交 0

通过率 --%
时间上限 内存上限
2000/1000MS(Java/Others) 262144/262144K(Java/Others)