C - Boxes and Candies（贪心）

Time Limit: 2 sec / Memory Limit: 256 MB

Score : 300300 points

Problem Statement

There are NN boxes arranged in a row. Initially, the ii-th box from the left contains aiai candies.

Snuke can perform the following operation any number of times:

Choose a box containing at least one candy, and eat one of the candies in the chosen box.

His objective is as follows:

Any two neighboring boxes contain at most xx candies in total.

Find the minimum number of operations required to achieve the objective.

Constraints

2≤N≤1052≤N≤1050≤ai≤1090≤ai≤1090≤x≤1090≤x≤109

---

Input

The input is given from Standard Input in the following format:

NN xx a1a1 a2a2 ...... aNaN

Output

Print the minimum number of operations required to achieve the objective.

---

Sample Input 1 Copy

Copy

3 3 2 2 2

Sample Output 1 Copy

Copy

1

Eat one candy in the second box. Then, the number of candies in each box becomes (2,1,2)(2,1,2).

---

Sample Input 2 Copy

Copy

6 1 1 6 1 2 0 4

Sample Output 2 Copy

Copy

11

For example, eat six candies in the second box, two in the fourth box, and three in the sixth box. Then, the number of candies in each box becomes (1,0,1,0,0,1)(1,0,1,0,0,1).

---

Sample Input 3 Copy

Copy

5 9 3 1 4 1 5

Sample Output 3 Copy

Copy

0

The objective is already achieved without performing operations.

---

Sample Input 4 Copy

Copy

2 0 5 5

Sample Output 4 Copygeininm

Copy

10

All the candies need to be eaten.

题意：给你n个数，保证任意相邻的两个数的和不超过x，（每一次操作只能让其中的一个数-1）问至少要操作多少次。

思路：直接贪心就行了

代码：

#include<bits/stdc++.h> #define ll long long using namespace std; ll a[100009]; int main() { ll n,x; cin>>n>>x; for(ll i=1;i<=n;i++) { cin>>a[i]; } ll sum=0; if(a[1]>x) { sum+=a[1]-x; a[1]=x; } for(ll i=2;i<=n;i++) { if(a[i]+a[i-1]>x) { sum+=(a[i]+a[i-1]-x); a[i]-=(a[i]+a[i-1]-x); } } cout<<sum<<endl; }