【C++贪心】Boxes and Candies

题目描述

There are N boxes arranged in a row. Initially, the i-th box from the left contains ai 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 x candies in total.
Find the minimum number of operations required to achieve the objective.

Constraints
2≤N≤10^5
0≤ai≤10^9
0≤x≤10^9

输入

The input is given from Standard Input in the following format:
N x
a1 a2 … aN

输出

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

样例输入 Copy

3 3
2 2 2

样例输出 Copy

1

提示

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

#include <cstdio>
const int N = 1e5 + 10;
int a[N];
int main()
{
	int n, x;
	scanf("%d%d", &n, &x);
	long long ans = 0;
	for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
	for (int i = 1; i <= n; i++)
	{
		if (a[i] + a[i - 1] > x)
		{
			ans += a[i] + a[i - 1] - x;
			a[i] -= a[i] + a[i - 1] - x;
		}
	}
	printf("%lld\n", ans);
	return 0;
}