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:
His objective is as follows:
Find the minimum number of operations required to achieve the objective.
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.
从前往后遍历盒子，当遍历至第i个盒子时，设法让对任意0<j<i，有a[j]+a[j+1]<=x，则只要考虑a[i]+a[i+1]是否小于等于x。若不满足，则优先从a[i+1]里拿(已知a[i-1]+a[i]<=x，但a[i+1]+a[i+2]有可能大于x)，这样能保证操作数最少。
代码如下：
#include <iostream> #include <cstdio> #define maxn 100010 #define ll long long using namespace std; int a[maxn]; int n,x; ll ans; int main() { scanf("%d%d", &n, &x); for (int i = 1; i <= n; i++) scanf("%d", a + i); for (int i = 1; i < n; i++) { while (a[i] + a[i + 1] > x) { if (a[i + 1]) { if (a[i] >= x )//只从a[i+1]拿不满足要求 { ans += a[i + 1]; a[i + 1] = 0;//不要傻乎乎地每次-1，否则会TLE } else { ans += a[i] + a[i + 1] - x; a[i + 1] = x - a[i]; } } else//a[i+1]==0 { ans += a[i] - x; a[i] = x; } } } printf("%lld", ans); return 0; }
AtCoder Beginner Contest 048 C Boxes and Candies
原文：https://www.cnblogs.com/yangyi2120/p/14614535.html