題目：

題目描述

小 A 有?n?個(gè)糖果盒，第?i?個(gè)盒中有?ai?顆糖果。

小 A 每次可以從其中一盒糖果中吃掉一顆，他想知道，要讓任意兩個(gè)相鄰的盒子中糖的個(gè)數(shù)之和都不大于?x，至少得吃掉幾顆糖。

輸入格式

輸入的第一行是兩個(gè)用空格隔開的整數(shù)，代表糖果盒的個(gè)數(shù)?n?和給定的參數(shù)?x。

第二行有?n?個(gè)用空格隔開的整數(shù)，第?i?個(gè)整數(shù)代表第?i?盒糖的糖果個(gè)數(shù)?ai。

輸出格式

輸出一行一個(gè)整數(shù)，代表最少要吃掉的糖果的數(shù)量。

輸入輸出樣例

輸入?

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 盒中的一個(gè)糖果即可。

樣例輸入輸出 2 解釋

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

數(shù)據(jù)規(guī)模與約定

• 對于?$30\%$?的數(shù)據(jù)，保證?n≤20，ai,x≤100。

• 對于?$70\%$?的數(shù)據(jù)，保證?n≤103，ai,x≤105。

• 對于?$100\%$?的數(shù)據(jù)，保證?2≤n≤105，ai,x≤109。

簡單理解：

有n個(gè)數(shù)，每兩個(gè)數(shù)之間不能超過x，求最少要減去多少才能滿足前面的規(guī)定；

思路：

這題的知識點(diǎn)涉及到了模擬和貪心

一組一組的來判斷是否大于x(一組就是第一個(gè)和第二個(gè)，第二個(gè)和第三個(gè)……),如果大于那么就要減糖果，現(xiàn)在就要想是要減第一個(gè)還是第二個(gè)呢？如果減一組中的第一個(gè)就不是最優(yōu)解，因?yàn)闇p第二個(gè)是能同時(shí)減少兩組的數(shù)量的，就第一組和第二組來說，第一個(gè)數(shù)是只被第一組包含的，二第二個(gè)數(shù)被一二兩組同時(shí)包含，以此類推，所以減去第二個(gè)數(shù)是更優(yōu)的選擇

易錯(cuò)點(diǎn)：

1. 不要循環(huán)慢慢的減（“--box[i]”這樣）會(huì)超時(shí)，第一次就是這樣錯(cuò)的，要用算出來的公式

2. 要把計(jì)數(shù)變量寫在減糖果操作的前面，減糖果的操作會(huì)改變box的值

前排說明一下公式（其實(shí)很簡單）：

（1）box[i]+box[i+1]-x? 就是這一組糖果超過x的數(shù)量

（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]){//判斷是否兩個(gè)盒子的糖果加起來超過了x，還判斷了超過的數(shù)量是否大于第二個(gè)盒子的數(shù)量

? ? ? ? ? ? /*這里是超過數(shù)量沒有超過第二個(gè)盒子的數(shù)量*/

? ? ? ? ? ? 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]){

? ? ? ? ? ? /*這里是超過數(shù)量超過了第二個(gè)盒子的數(shù)量*/

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

? ? ? ? ? ? box[i]=x;（3）

? ? ? ? ? ? box[i+1]=0;

? ? ? ? }

? ? }

? ? cout<<cnt;

}