题解 【CF1139B Chocolates】
TRZ_2007
2021-04-21 18:52:22
**[题解 【CF1139B Chocolates】](https://www.luogu.com.cn/problem/CF1139B)**
# Solution
显然，关于任意的 $x_i$，它都会比前面的所有 $x_j$ 都要大**或者**它后面的数全部都是 0，因为我们要求让 $\sum x_i$，达到最大值，故我们希望让 0 少一些，即让这个数列 $x$ 下降的慢一些，因此应该让现在的 $a_i$ 和 $x_{i + 1} - 1$ 两个数进行比较，取其中的最小值作为 $x_i$。注意 $x_i$ 根据题意大于等于 0，判断一下就解决了。
~~最后贴一下最优解代码。~~
~~记得开 long long。~~
# Code
```cpp
#include <cstdio>
#include <cctype>
using namespace std;
#define gc getchar
inline int read() {
int c = gc(), t = 1, n = 0;
while(isspace(c)) { c = gc(); }
if(c == '-') { t = -1, c = gc(); }
while(isdigit(c)) { n = n * 10 + c - '0', c = gc(); }
return n * t;
}
#undef gc
const int N = 2e5 + 9;
typedef long long ll;
#define min(a,b) a > b ? b : a
ll a[N],x,sum;
int n;
int main() {
n = read(); x = 1e10;
for(int i = 1;i <= n;i++) a[i] = read();
for(int i = n;i >= 1;i--) {
x = min(a[i],x - 1); //获得本次的xi
sum += (x > 0) ? x : 0; //任意的xi都大于等于0
}
printf("%lld\n",sum);
return 0;
}
```