【NOIP模拟赛】买汽水

2014年10月29日1,2370

【问题描述】

暑期集训一共N天,大家都辛苦了,Symbol准备给大家买汽水,但是钱只有M。

每天买汽水的花销都是不固定的,如果不够钱,买到的汽水不够大家一起喝,那样子不太好对不对?所以我们要买的话,就得让每个人都能喝到汽水要不我们那天就不买了。现在给出每天买汽水的花销,请问我们一共最多能够花掉Symbol多少钱呢?

暑假最多不超过40天,Symbol给大家花的钱最多有一亿。

 

【输入】

输入第一行有两个整数N,M。 1<=N<=40,0<=M<=100000000。

接下来一行有N个数,表示某一天的汽水花销。每天汽水的花销p<=100000000。

 

【输出】

输出一个整数,表示我们能够花掉Symbol多少钱。

 

【输入输出样例一】

drink.in drink.out
3 101 2 3 6

 

【输入输出样例二】

drink.in drink.out
4 104 3 5 11 9

 

【数据描述】

对于10%的数据,N<=10。

对于30%的数据,N<=20。

对于60%的数据,N<=30。

对于100%的数据,N<=40。

题解

折半搜索,一半放进平衡树,另一半找M-x的前驱后继更新答案

当然排序后二分也是可以的