【NOIP模拟赛】工资

2014年9月6日1,3112

聪哥在暑假参加了打零工的活动,这个活动分为n个工作日,每个工作日的工资为Vi。有m个结算工钱的时间,聪哥可以自由安排这些时间,也就是说什么时候拿钱,老板说的不算,聪哥才有发言权!(因为聪哥是土豪,他是老板的老板)

聪哥不喜欢身上一次性有太多的钱,于是他想安排一下拿钱的时间,使他一次性拿的钱中最大的最小。(最后一天一定要领钱)

输入

第一行 2个数 n,m

接下来n行,每行一个数,代表Vi.

输出

最小的最大钱数。

样例输入

7 5

100

400

300

100

500

101

400

样例输出

500

 

样例说明

100 400//300 100//500//101//400//

“//”表示老大要去拿钱。

 

数据范围

20%   1<=n<=20

另 20% 1<=n<=50,Vi的和不超过1000

100% 1<=n<=100,000,m<=n,Vi<=10,000

 

二分答案+判断。。

 

  • Leon2015年11月1日 下午12:00 回复

    这道题能用划分型的DP吗?

    #1  
    • hzwer2015年11月1日 下午10:57 回复

      可能不行

      #11