题解 【CF1139B Chocolates】

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

#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;
}