戴德兰

2387 戴德兰

1. 1 秒  
2. 131,072 KB  
3. 5 分  
4. 1 级题

牛牛非常喜欢赶deadline。

输入n, c, d

一共有n个任务，第i个任务需要a[i]分钟完成

特别的，在最后d分钟，牛牛的效率会变成双倍（耗时变为一半）

可能出现一个任务前半部分不在最后d分钟，后半部分在最后d分钟

那么只有在最后d分钟的后半部分效率会变为双倍。

牛牛希望在c分钟内完成的任务尽可能多，问最多可以完成多少个任务。

耗时变为一半，是不取整的，如果出现0.5，那么就是0.5。



对于100%的数据，1 <= n <= 10000, 1 <= d <= c <= 100000, 1 <= a[i] <= c。

对于40%的数据，1 <= n <= 20。

对于70%的数据，1 <= n <= 1000, 1 <= c <= 1000。

 收起

输入

输入第一行三个整数n, c, d。
接下来一行n个整数a[i]。

输出

输出一行一个整数，表示答案。

输入样例

4 10 5
8 10 1 2

输出样例

3

思路：最后d分分钟双倍相当于c加了d；

贪心从小到大完成任务

#include
#include
using namespace std;
int a[10005];
int main(){
int n,c,d;
cin>>n>>c>>d;
c=c+d;
for(int i=1;i<=n;i++)
cin>>a[i];
sort(a+1,a+1+n);
int sum=0;
for(int i=1;i<=n;i++){if(c>a[i]){sum++;c-=a[i];}elsebreak;
}
cout<endl;return 0;
}