洛谷 P3817 小A的糖果

https://www.luogu.com.cn/problem/P3817

题目描述

小 A 有 nn 个糖果盒，第 ii 个盒中有 a_iai​ 颗糖果。

小 A 每次可以从其中一盒糖果中吃掉一颗，他想知道，要让任意两个相邻的盒子中糖的个数之和都不大于 xx，至少得吃掉几颗糖。

输入格式

输入的第一行是两个用空格隔开的整数，代表糖果盒的个数 nn 和给定的参数 xx。

第二行有 nn 个用空格隔开的整数，第 ii 个整数代表第 ii 盒糖的糖果个数 a_iai​。

输出格式

输出一行一个整数，代表最少要吃掉的糖果的数量。

输入输出样例

输入 #1复制

3 3
2 2 2

输出 #1复制

1

输入 #2复制

6 1
1 6 1 2 0 4

输出 #2复制

11

输入 #3复制

5 9
3 1 4 1 5

输出 #3复制

0


分析
贪心策略：比较两堆，优先拿靠后盒子的糖果，因为会更多影响后面 又是一道不开long long 见祖宗

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;

int n,x;
int a[100005];
int ans;

signed main()
{
    int n,x;
    cin>>n>>x;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    for(int i=2;i<=n;i++)
    {
        if(a[i]+a[i-1]>x)
        {
            ans+=abs(x-(a[i]+a[i-1]));//拿走的 
            a[i]-=abs(x-(a[i]+a[i-1]));//从后一堆拿 
        }
    }
    cout<<ans<<endl;
    return 0;
}