P3817 小A的糖果

Portal.

贪心。

注意到这里的盒子不会被删除，只会改变盒子的值。问题立刻简单化了。对于一组相邻的糖果个数和大于 $x$ 的盒子组，优先吃掉靠后的盒子。

证明正确性也很显然，因为减少后面的盒子的糖果数可以使得后面的情况更优。

#include <bits/stdc++.h>
using namespace std;
#define int long longconst int maxn=1e5+5;
int a[maxn];signed main()
{int n,x;cin>>n>>x;for(int i=1;i<=n;i++) cin>>a[i];int ans=0;if(a[1]>x) ans+=a[1]-x,a[1]=x;for(int i=2;i<=n;i++)if(a[i]+a[i-1]>x) ans+=a[i]+a[i-1]-x,a[i]=x-a[i-1];cout<<ans;return 0;
}