传说神农为拯救黎民苍生尝草药无数。现在神农收集了n株不同种类的草药,编号依次为1~n。他为了了解草药的药理,不得不亲自尝试。每株草药都有其对应的功效a i ​ (−10 9 ≤a i ​ ≤10 9 ),功效为负时,草

药有毒,有可能会导致神农死亡。神农可以选择一些草药进行尝试,但是他不想要尝试太多,因为太多的尝试可能会导致他的生命危险。于是他决定尝试一些草药,使得尝试过的所有草药的功效之和的绝对值不超过k(0≤k≤10 9 )。请问他最多能尝试多少株草药呢?

输入描述:
第一行两个整数n,k(1≤n≤10 5 ,0≤k≤10 9 )。

第二行n个数,第i个数为a i ​ (−10 9 ≤a i ​ ≤10 9 )。

输出描述:
输出神农最多能尝试的草药数量。

示例1
输入
5 6
2 -3 5 1 6
输出
3

示例2
输入
5 3
2 -3 5 1 6
输出
1

备注:
在样例1中,神农最多能选择尝试第1、第2、第4株草药,此时尝试的草药的功效值之和为2+（−3）+1=0,不超过6。如果他再尝试一株草药,那么草药的功效值之和就会超过6,所以最多只能尝试3株草药。

相关问题

C++实现：现在，神农从１～n依次有选择性地品尝各株草药（对于某株草药，神农选择品尝或者不品尝），问：在神农不休克的前提下，最多可以品尝多少株草药？ 输入格式: 第一行输入一个正整数n（0≤n≤2×105），代表草药的总数。 第二行输入n个以空格隔开的整数，第i个整数ai​代表第i株草药的功效。 输出格式: 在一行中输出一个整数，表示神农可以品尝草药的最大数目。

这道题可以使用贪心算法来解决，每次选择功效最大的草药。

具体实现如下：

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 2e5 + 10;

int n;
int a[N];

int main()
{
    cin >> n;
    for(int i = 0; i < n; i++)
        cin >> a[i];

    sort(a, a + n); // 将草药按照功效从小到大排序

    int res = 0; // 记录神农品尝的草药数量
    for(int i = 0; i < n; i++)
    {
        if(a[i] > res + 1) // 如果当前草药的功效大于神农已经品尝的草药数量加上1，则无法再品尝
            break;
        res++; // 否则神农品尝该草药
    }

    cout << res << endl;

    return 0;
}

时间复杂度为O(nlogn)，主要是排序的复杂度。

C++实现输入描述: 第一行两个整数n,k(1≤n≤10 5 ,0≤k≤10 9 )。 第二行n个数,第i个数为a i ​ (−10 9 ≤a i ​ ≤10 9 )。 输出描述: 输出神农最多能尝试的草药数量。 示例1 输入 5 6 2 -3 5 1 6 输出 3 示例2 输入 5 3 2 -3 5 1 6 输出 1

这道题可以使用二分法来解决。首先对草药的价值进行排序，然后二分出一个值 mid，表示神农能够尝试的最大草药价值。接下来遍历整个草药数组，将草药价值大于等于 mid 的草药都加入到一个累加器中，如果累加器中的值超过了 k，则说明神农不能尝试的草药的价值需要小于 mid，此时将二分的上界调整为 mid-1，否则将二分的下界调整为 mid+1。最后得到的就是神农最多能尝试的草药数量。

下面是代码实现：