【洛谷】P3817 小A的糖果 （贪心算法）

【洛谷】P3817 小A的糖果 （贪心算法）

算法思路
怎么说呢，一看到这个题有点熟悉，但是又一时间想不起来类似那道题。这也是一道一次就可以AC的题（忽略我的一个小问题）
第一遍定义没有定义Long Long导致有2个测试点没过，然而问题不大，借此告诫同学们记得看条件。
典型的贪心，第一个为临界点，其余每个不考虑后面，让他取到可以取的最大值，后面的不管，即贪心
对于从第二个开始，如果前面一个小于X，则他有两种情况：1.他小于 X 与 X与上一个的差 即a【i】< flag 则他不需要减少 2.多与flag，则sum加上超额的并且a【i】改变 flag改变。

先上一个我AC过后的简化版，因为第一遍求过所以没有很简化，后来又想了想去除掉了一部分多余的，先给大家增加一些信心，具体思路还是看后面的代码比较好

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n,x,a[100005]; cin>>n>>x;
	long long sum=0;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=n;i++)  
	{
		if(a[i]+a[i+1]>x)
        {
            sum+=a[i+1]+a[i]-x;
            a[i+1]=x-a[i];
        }
	}
	cout<<sum;
	return 0; 
}

#include<bits/stdc++.h>
using namespace std;
long long a[100005];
int main()
{
	int n,x;
	cin>>n>>x;
	for(int i=1;i<=n;i++)
	cin>>a[i];
	long long sum=0,flag;
	if(x-a[1]<0) //判断第一个是否大于X 
	{
		sum+=abs(x-a[1]); //大于 则a【1】变为x sum初始值变 
		a[1]=x;
		flag=0;
	}
	else{                 //否则 flag初始值为差值 
		flag=x-a[1];
	}
	
	for(int i=2;i<=n;i++)  //从第二个开始循环 
	{
		if(a[i]>flag){  
			sum+=a[i]-flag;
			a[i]=flag;
			flag=x-a[i];
		}
		else{
			flag=x-a[i];
		}
		
	}
	cout<<sum;
	return 0; 
}