白浅吃糖果(easy version)

描述#

白浅喜欢吃糖，有一天她到了一个可以免费吃糖果的游乐园。游乐园摆放着一排共n个糖果，对于任意的i(1<=i<n-1),第i个糖果与第i+1个糖果相邻。第i个糖果具有一个甜度值ai。妈妈说吃甜食太多了会得蛀牙，所以白浅吃的糖果的甜度值总和不能超过k。她可以以任意的顺序吃糖，请问她最多能吃多少个糖果？

输入#

第一行给出两个正整数n，k (1<=n<=2e5,1<=k<=1e9)，意义如题面所描述第二行有n个整数，分别代表每一个糖果的甜度值a(1<=a<=1e9)

输出#

输出一行一个整数代表白浅最多可以吃掉的糖果数。

输入样例 1 #

1
3 5
2
2 4 2

输出样例 1#

1
2

基本思路#

1. 对于这道题，显而易见，可以以任意的顺序拿糖；也就是说，可以不连续地挑选其中的几颗糖。
2. 对于每一颗糖来说，都有一个甜度值。所有被挑选出来的糖的甜度值必须小于k，且挑出的糖要尽量多。
3. 可以想到，就是把甜度值从小到大排列出来，从前往后选糖直到甜度值之和大于k为止。

代码实现#

1
#include<bits/stdc++.h>
2
using namespace std;
3
long long n,k;
4
long long a&#91;200005];
5
long long cnt=0;
6
long long sum=0;
7
int main(){
8
  cin>>n>>k;
9
  for(long long i=1;i<=n;i++){
10
    cin>>a&#91;i];
11
  }
12
  sort(a+1,a+1+n);
13
  for(long long i=1;i<=n;i++){
14
    if(sum+a&#91;i]>k)break;
15
    else{
16
      cnt++;
17
      sum+=a&#91;i];
18
    }
19
  }
20
  cout<<cnt;
21
  return 0;
22
}

warning 注意事项 请注意数据范围：n，k (1<=n<=2e5,1<=k<=1e9)。所以变量可以使用long long，数组也要开到2e5。