蓝桥杯备考：贪心算法之小A的糖果
·
这道题是道贪心的问题，我们要相邻的两个盒子糖果总数不超过某个数
如果两个盒子糖果总数超过那个数了，我们只要让小A吃掉sum-x个糖果就行了
第二个细节是，我们要让小A吃掉哪个盒子里的糖果?吃靠左的话，靠右的加起来糖果总数偏大了，我们要求吃的糖果最少，所以应该吃掉靠右的盒子的糖果
第三个事情就是，如果吃的糖果超过了靠右盒子的量怎么办？那不是出现负数了吗
这种情况，我们只要让第0个和第一个盒子的糖果加起来，然后吃掉1盒子多余的糖果就行了
实现一下我们的代码
#include <iostream>
using namespace std;
typedef long long ll;
ll n,x;
const int N = 1e5+10;
ll a[N];
int main()
{
cin >> n >> x;
for(int i = 1;i<=n;i++)
{
cin >> a[i];
}
ll sum = 0;
for(int i = 1;i<=n;i++)
{
if(a[i]+a[i-1]>x)
{
sum+=a[i]+a[i-1]-x;
a[i]=x-a[i-1];
}
}
cout << sum << endl;
return 0;
}
北京人形旗下天工造物具身智能开源社区，聚焦具身天工与慧思开物两大平台
更多推荐
2
0- 0
已为社区贡献6条内容
所有评论(0)