题目描述
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≤105
0≤ai≤109
0≤x≤109
输入
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.
提示
Eat one candy in the second box. Then, the number of candies in each box becomes (2,1,2).
问题大意：给定序列，可以一次改变一个值，使得任意相邻的两个之和小于等与k；
问题解析：先两个两个的改变，一定先改变两者后面的那个，因为后面的那个对后面的有贡献（比如说a1,a2,a3,先遍历a1和a2，判断是否符合要求，如果不符合要求，要先减少a2,因为a2还对a1有贡献）,注意不能让a2变成负数
#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
inline int read() {int x=0,f=1;char c=getchar();while(c!=‘-‘&&(c<‘0‘||c>‘9‘))c=getchar();if(c==‘-‘)f=-1,c=getchar();while(c>=‘0‘&&c<=‘9‘)x=x*10+c-‘0‘,c=getchar();return f*x;}
typedef long long ll;
const int maxn=5e5+10;
const int M=1e7+10;
const int INF=0x3f3f3f3f;
ll n,x;
ll a[maxn];
void inint(){
cin>>n>>x;
for(int i=0;i<n;i++){
cin>>a[i];
}
}
int main(){
inint();
ll sum=0;
for(int i=1;i<n;i++){
if(a[i]+a[i-1]>x){
if(x-a[i-1]>=0){
sum+=a[i]-(x-a[i-1]);
a[i]=(x-a[i-1]);
}
else{
sum+=(a[i]+a[i-1]-x);
a[i]=0;
}
}
}
printf("%lld",sum);
return 0;
}
