C语言之小A的糖果

题目描述

小 A 有 $n$ 个糖果盒，第 $i$ 个盒中有 ai​ 颗糖果。

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

输入格式

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

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

输出格式

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

输入
3 3
2 2 2
输出
1

输入
6 1
1 6 1 2 0 4
输出
11

输入
5 9
3 1 4 1 5
输出
0

说明/提示

样例输入输出 1 解释

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

---

样例输入输出 2 解释

第 2 盒糖吃掉 $6$ 颗，第 4 盒吃掉 $2$ 颗，第 6 盒吃掉 $3$ 颗。

解题历程

#include<stdio.h>
int main()
{int m,n;while(scanf("%d%d",&m,&n)!=EOF){//输入多组数据int i;int count;int sum=0;int a[m];for(i=0;i<m;i++){scanf("%d",&a[i]);//输入三组糖果数量}for(i=0;i<m-1;i++){int b=a[i]+a[i+1];//计算相邻两组糖果的总个数if(b<=n){continue;}else{//如果相邻总糖果个数大于给定的参数count=b-n;//多出来的糖果个数即为要吃掉的糖果数量a[i+1]=a[i+1]-count; 就是相加的两组中右边的那个吃完之后的剩余数量，再去与后面的那个进行计算sum=sum+count;//最后要吃的总个数}}printf("%d\n",sum);}return 0;
}
//上述代码结果是正确的，但是只有80%的正确率。

真正的100%正确率

#include<stdio.h>
int main()
{int m,n;while(scanf("%d%d",&m,&n)!=EOF){int i;int count;long long sum=0.0;//防止总数太大，超出int限度int a[m];for(i=0;i<m;i++){scanf("%d",&a[i]);}for(i=0;i<m-1;i++){int b=a[i]+a[i+1];if(b>n){count=b-n;//到目前为止，和我的想法是一样的。if(a[i+1]>=count){//要确保两组中右边的那个糖果数量大于要吃掉的糖果数量，否则不能直接用概述减去要吃掉的糖果数。a[i+1]=a[i+1]-count; sum=sum+count;} else{//如果真的右边的糖果数量少于要吃掉的糖果数量，就不能直接减。这就是我一开始写代码没考虑到的部分int c=a[i+1];//因为要把a[i+1]变为0，所以要先标记再变为0，这样才不会影响后面用a[i+1]a[i+1]=0;//肯定先要把右边的变为0，然后再去吃前面的，这样就保证吃最少的糖果，符合题意int d=count-c;//这是吃掉右边的糖果之后还需要吃掉的糖果数量，这就要吃掉左边的糖果。a[i]-=d;//左侧的糖果变成了吃掉后剩余的糖果。sum+=count;这也要加到sum中去}}}printf("%lld\n",sum);}return 0;
}

 特别注意的是要考虑到所有可能出现的情况，即中间的数不够减。因为糖果总数是两边加起来的，不一定右边的数大于左边的数。