Riverside Curio

女爷i 2022-05-27 03:35 81阅读 0赞

题目链接：http://codeforces.com/problemset/problem/924/C

/*看懂题目 只要满足两个条件就OK啦
    1. s[i]>=s[i+1]-1 && s[i]>=a[i]+1;(逆序遍历)
    2.s[i]>=s[i-1];(正序遍历)
    */
    #include<stdio.h>
    int main()
    {
        int n;
        int a[100005],s[100005];
        while(scanf("%d",&n)!=EOF)
        {
            for(int i=1;i<=n;i++)
            {
                scanf("%d",&a[i]);
            }
            s[1]=1;
            int now=0;
            for(int i=n;i>0;i--)
            {
                int x=now-1;
                int y=a[i]+1;
                if(x>y)
                {
                    s[i]=x;
                }
                else
                {
                    s[i]=y;
                }
                now=s[i];
            }
            long long sum=0; //注意
            for(int i=1;i<=n;i++)
            {
                if(s[i]<s[i-1])
                {
                    s[i]=s[i-1];
                }
                sum=sum+s[i]-a[i]-1;
            }
            printf("%lld\n",sum);
        }
        return 0;
    }

Riverside Curio

发表评论取消回复

还没有评论，来说两句吧...

相关阅读

相关推导 Riverside Curio:CodeForces - 957D 924C 472div2

相关 Riverside Curio