P3817 小A的糖果

题目描述

小 A 有

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

输入格式

输入的第一行是两个用空格隔开的整数，代表糖果盒的个数

第二行有

输出格式

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

输入输出样例

输入 #1

3 3
2 2 2

输出 #1

输入 #2

6 1
1 6 1 2 0 4

输出 #2

输入 #3

5 9
3 1 4 1 5

输出 #3

说明/提示

样例输入输出 1 解释

吃掉第 2 盒中的一个糖果即可。

样例输入输出 2 解释

第 2 盒糖吃掉

数据规模与约定

对于
对于 $10^3, ai, x ≤ 10^5$
对于 $10^5, 0 ≤ ai,x ≤ 10^9$

#include<iostream>
using namespace std;

const int MAXN = 1e5 + 5;
long long candy[MAXN];        // 糖果数，注意！！！ 这题一定要 long long  

int main()
{
    long long n, num = 0;        // 糖果盒数量 ，要吃掉的糖果数 
    long long x;                // 题目要求的给定参数 x ，即相邻两项相加不得超过 x 
    cin >> n >> x;
    for(int i = 1; i <= n; i++)
    {
        cin >> candy[i];
    }
    
    for(int i = 1; i <= n; i++)
    {
        if(candy[i] > x)                    // 先把 糖果数超过 x 的糖果盒吃掉一部分，只剩余 x 个糖果 
        {                                    // 因为即使周围 0 个糖果，那么这相邻两项相加，也依然超过 x 
            num = num + candy[i] - x;        // 吃掉的糖果数 
            candy[i] = x;
        }
    }
    
    for(int i = 2; i <= n; i++)                // 模拟相邻两项相加
    {                                        // 从第一项开始，相邻两项如果超过 x，要吃掉后面那一个
        if(candy[i] + candy[i - 1] > x)        // 模拟 
        {
            num = num + candy[i] + candy[i - 1] - x;
            candy[i] = x -  candy[i - 1];
        }
    }
    
    cout << num << endl;
    
    return 0;
 } 
 
// 因为是相邻两项的糖果数相加不得超过 x
// 那么本题在于如何才能吃掉的更少
// 贪心方式为：从第一项开始 如果相邻两项和大于 x ，那么吃掉 后面那一盒的部分糖果
// 因为 后面的那一盒有两个相邻，而第一盒只有一个相邻
// 同理，也可以从最后一盒往前看，那就是吃掉前面那一盒的糖果