洛谷题单指南-贪心-P3817 小A的糖果

原题链接：https://www.luogu.com.cn/problem/P3817

题意分析：吃最少的糖果，保证相邻糖果数之和不大于x，需要某种贪心策略。

解题思路：

依次遍历相邻两盒糖果

如果糖果数之和大于x，必须要吃点一部分，使得糖果数之和刚好等于x

贪心策略是：优先吃后一盒糖果，因为这样可以更利于后续的判断成立

注意：

1、如果后一盒糖果不够吃，要继续吃前一盒糖果

2、总数可能爆int，需要long long

100分代码：

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

const int N = 1e5 + 5;

int a[N];
int n, x;
long long ans;

int main()
{
    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) //依次看两个数的和与x的关系
        {
            int t = a[i] + a[i-1] - x;
            if(a[i] >= t) a[i] -= t; //优先从后一个数减
            else a[i] = 0, a[i-1] -= (t - a[i]); //后一个数不够减再从前一个数减

            ans += t;
        }
    }

    cout << ans;

    return 0;
}