洛谷P3817 小A的糖果——贪心算法

左手的ㄟ右手 2022-11-12 01:40 151阅读 0赞

## 题目描述 ##

小 A 有 n 个糖果盒，第  i i i 个盒中有  a i a\_i ai 颗糖果。

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

## 输入格式 ##

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

第二行有  n n n 个用空格隔开的整数，第  i i i 个整数代表第  i i i 盒糖的糖果个数  a i a\_i ai。

## 输出格式 ##

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

## 输入输出样例 ##

**输入 \#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 盒糖吃掉 6 颗，第 4 盒吃掉 2 颗，第 6 盒吃掉 3 颗。

**数据规模与约定**  
对于  30 % 30\\% 30% 的数据，保证  n ≤ 20 n \\leq 20 n≤20， a i , x ≤ 100 a\_i, x \\leq 100 ai,x≤100。

对于  70 % 70\\% 70% 的数据，保证  n ≤ 1 0 3 n \\leq 10^3 n≤103， a i , x ≤ 1 0 5 a\_i, x \\leq 10^5 ai,x≤105 。

对于 100%100% 的数据，保证  2 ≤ n ≤ 1 0 5 2 \\leq n \\leq 10^5 2≤n≤105 ， 0 ≤ a i , x ≤ 1 0 9 0 \\leq a\_i, x \\leq 10^9 0≤ai,x≤109。

--------------------

此题需要注意数字的表达方式，int不行，需要用long long

AC正解

#include <algorithm>
    
    #include <iostream>
    #define LL long long
    using namespace std;
    
    int main()
    { 
        LL n, x;
        cin >> n >> x;
        LL *arr = new LL[n + 10]; // 动态分配数组，节省内存
        for (int i = 0; i < n; i++)
        { 
            cin >> arr[i];
        }
        // sort(arr, arr + n);
        LL cnt = 0;
        // if (arr[0] > x)
        // { 
        // cnt += arr[0] - x;
        // arr[0] -= cnt;
        // }
        for (register int i = 1; i < n; i++)
        { 
            if ((arr[i - 1] + arr[i]) > x)
            { 
                cnt += arr[i - 1] + arr[i] - x;
                arr[i] -= arr[i - 1] + arr[i] - x;
            }
        }
        cout << cnt << endl;
        return 0;
    }