codeforces 957D Riverside Curio

题目链接：http://codeforces.com/contest/957/problem/D

题意：有一个水池，每天的水位会上升或者下降。每天需要在水位处划一道白线来记录当天的水位，如果水位处有白线，则不需要再划。然后给你一个长为n的数组m，mi表示在第i天观察到水位上方的白线的条数（不包括当前水位）。然后现在让你求这n天水位下方的白线的个数和。

分析：题目要你求所有天水位下方的白线的个数之和，其实我们可以知道每天水位下方的白线+每天水位下方的白线+1=当天的白线的个数，且相邻的两天白线的差值为0或1；于是我们可以先对水位上方的白线+1来记录每天的白线最少有多少条a[i]，且后一天的白线比当天多0或1条。这样需要给每天mi+1，然后a[i+1]=max(a[i],a[i+1])。然后逆着扫一遍，来确保a[i+1]-a[i]<=1；那么所有天中水位下方的白线的个数和=a[i]-m[i]-1，求和即可

AC代码：

#include<bits/stdc++.h>

using namespace std;

int a[100005],b[100006];
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    int m[100005];
    while(cin>>n){
        for(int i=1;i<=n;i++){
            cin>>m[i];
            a[i]=m[i]+1;
        }
        for(int i=2;i<=n;i++){
            a[i]=max(a[i],a[i-1]);
        }
        for(int i=n-1;i>=1;i--){
            a[i]=max(a[i],a[i+1]-1);
        }
        long long result=0;
        for(int i=1;i<=n;i++){
            result+=(a[i]-m[i]-1);
        }
        cout<<result<<endl;
    }
return 0;
}