文章

白浅吃糖果(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
2
3 5
2 4 2

输出样例 1

1
2

</p>

基本思路

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

</p>

代码实现

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

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

本文由作者按照 CC BY 4.0 进行授权

© Dignite. 保留部分权利。 由  提供CDN加速。

浙ICP备2023032699号 | 使用 Jekyll 主题 Chirpy