题解 P3817 【小A的糖果】 C++题解

· · 题解

模拟+贪心

这道题很简单，但是需要思考

当相邻的两盒大于x到时候，应该先吃那一盒呢？

答案：正着遍历，吃后面；反着遍历，吃前面！

为什么是这样的呢？

比如一个样例：

5 6

4 5 3 6 2

此时，若正着遍历，4+5>6，如果吃4（a[1]），就考虑不到a[3]，吃5(a[2])则一举两得。

下面是代码：

#include<bits/stdc++.h>
using namespace std;
long long ans; //一定要开long long!!!
int n,x,a[100002];
main() {
    cin>>n>>x; //输入
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<n;i++) //模拟,正着遍历
        if(a[i]+a[i+1]>x) {  //如果相邻两盒>x
            ans+=a[i+1]-x+a[i]; //就吃后面的
            a[i+1]=x-a[i];
        }
    cout<<ans; //输出
    return 0;   
}

求过！