洛谷 P3817 小A的糖果

题目链接:洛谷 P3817 小A的糖果

算法标签: 贪心模拟

题目

题目描述

小A有N个糖果盒,第i个盒中有a[i]颗糖果。

小A每次可以从其中一盒糖果中吃掉一颗,他想知道,要让任意两个相邻的盒子中加起来都只有x颗或以下的糖果,至少得吃掉几颗糖。

输入格式

第一行输入N和x。

第二行N个整数,为a[i]。

输出格式

至少要吃掉的糖果数量。

输入输出样例

输入 #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

说明/提示

样例解释1

吃掉第二盒中的糖果。

样例解释2

第二盒吃掉6颗,第四盒吃掉2颗,第六盒吃掉3颗。

30%的测试数据,2<=N<=20,0<=a[i], x<=100

70%的测试数据,2<=N<=1000,0<=a[i], x<=10^5

100%的测试数据,2<=N<=10^5,0<=a[i], x<=10^9

题解:

贪心

一道贪心思路的题。

首先我们可以考虑一个问题,如果对于最左侧的1号和2号盒子中的糖果,一定是吃2号盒子中的最优!!!(因为一号盒子不会对其他盒子再产生影响,但是二号盒子可以影响三号盒子)所以我们每次都吃掉后边一个盒子的糖果()。

符合贪心策略,我们找每一个盒子,如果两个盒子的和大于了给定的\(X\),那么我们就吃后一个盒子当中的糖果。统计\(ans\)记录吃的糖果数,最终输出即可。

不要忘记数据范围是需要开long long的!!!

AC代码

#include <bits/stdc++.h>

using namespace std;

long long n, m, ans, num[100100];

int main()
{
    scanf("%lld%lld", &n, &m);
    for (int i = 1; i <= n; i ++ )
    {
        scanf("%lld", &num[i]);
    }
    for (int i = 1; i < n; i ++ )
    {
        if (num[i] + num[i + 1] > m)
        {
            ans = ans + num[i] + num[i + 1] - m;
            num[i + 1] = m - num[i];
        }
    }
    printf("%lld\n", ans);
}
01-02 15:41