为了研究农场的气候, Betsy 帮助 FJ 做了 次气压测量并按顺序记录了结果 ()。Betsy 想找出一部分测量结果来总结整天的气压分布。她想用 个数 ()来概括所有测量结果。她想限制如下的误差:对于任何测量结果子集,每一个非此子集中的结果都会产生误差。总误差是所有测量结果的误差之和。更明确地说,对于每一个和所有 都不同的 :
Besty 给了最大允许的误差 ,找出最小的一部分结果使得误差最多为 。
第一行:两个空格分隔的数: 和 。
第 行:第 行包含一次测量记录:。
4 20 10 3 20 40
2 17
对于 的数据,,,,,。 Bessie 做了 次记录,分别为 ,,, .最大允许误差是 ,选择第二和第四次测量结果能达到最小误差 。第一次结果的误差是,第三次结果的误差是。
Usaco 2009 Jan Gold