P3817 小A的糖果（贪心，模拟）

题目：

题目描述

(相关资料图)

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

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

输入格式

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

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

输出格式

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

输入输出样例

输入 

3 32 2 2

输出 

1

输入 

6 11 6 1 2 0 4

输出 

11

输入 

5 93 1 4 1 5

输出 

0

说明/提示

样例输入输出 1 解释

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

样例输入输出 2 解释

第 2 盒糖吃掉 66 颗，第 4 盒吃掉 22 颗，第 6 盒吃掉 33 颗。

数据规模与约定

对于 30%30% 的数据，保证 n≤20，ai,x≤100。

对于 70%70% 的数据，保证 n≤103，ai,x≤105。

对于 100%100% 的数据，保证 2≤n≤105，ai,x≤109。

简单理解：

有n个数，每两个数之间不能超过x，求最少要减去多少才能满足前面的规定；

思路：

这题的知识点涉及到了模拟和贪心

一组一组的来判断是否大于x(一组就是第一个和第二个，第二个和第三个……),如果大于那么就要减糖果，现在就要想是要减第一个还是第二个呢？如果减一组中的第一个就不是最优解，因为减第二个是能同时减少两组的数量的，就第一组和第二组来说，第一个数是只被第一组包含的，二第二个数被一二两组同时包含，以此类推，所以减去第二个数是更优的选择

易错点：

1. 不要循环慢慢的减（“--box[i]”这样）会超时，第一次就是这样错的，要用算出来的公式

2. 要把计数变量写在减糖果操作的前面，减糖果的操作会改变box的值

前排说明一下公式（其实很简单）：

（1）box[i]+box[i+1]-x  就是这一组糖果超过x的数量

（2）box[i+1]=x-box[i]   是:   box[i+1] = box[i+1] - (box[i] + box[i+1] - x ) 的简化

（3）box[i]=x   是：box[i] = box[i] - [ (box[i] + box[i+1] - x) - box[i+1]] 的简化

代码：

#include <iostream>

using namespace std;

int box[100000],cnt;

int main()

{

int n,x;

cin>>n>>x;  

for(int i=0;i<n;i++)cin>>box[i];/*输入*/

for(int i=0;i<n-1;i++){

if(box[i]+box[i+1]>x&&box[i]+box[i+1]-x<=box[i+1]){//判断是否两个盒子的糖果加起来超过了x，还判断了超过的数量是否大于第二个盒子的数量

/*这里是超过数量没有超过第二个盒子的数量*/

cnt+=box[i]+box[i+1]-x;（1）

box[i+1]=x-box[i];（2）

}else if(box[i]+box[i+1]>x&&box[i]+box[i+1]-x>box[i+1]){

/*这里是超过数量超过了第二个盒子的数量*/

cnt+=box[i]+box[i+1]-x;

box[i]=x;（3）

box[i+1]=0;

}

}

cout<<cnt;

}

标签： xbox 就是这样 以此类推