当前位置: 首页 > 工具软件 > Curio > 使用案例 >

[Codeforces947D]Riverside Curio(思维)

方绪
2023-12-01

Description

题目链接

Solution

设S[i]表示到第i天总共S[i]几个标记,

那么满足S[i]=m[i]+d[i]+1

m[i]表示水位上的标记数,d[i]表示水位下的标记数

那么可以发现,S[i]满足非严格递增,且相邻2个相差不超过1

由此可转化题目,

给你n个数,可以给任意数加上任意正整数,要求使得最后使这个数列满足S[i]的条件

问最少加多少,这样就简单了

注意开long long

Code

#include<cstdio>

int n,A[100010];
long long Ans;

int main() {
    scanf("%d",&n);
    for(int i=1;i<=n;++i) {
        scanf("%d",&A[i]);
        if(A[i]<A[i-1]) Ans+=A[i-1]-A[i],A[i]=A[i-1];
    }
    for(int i=n;i>=2;--i) if(A[i]-A[i-1]>1) Ans+=A[i]-A[i-1]-1,A[i-1]=A[i]-1;
    printf("%I64d\n",Ans);
    return 0;
}

转载于:https://www.cnblogs.com/void-f/p/8653208.html

 类似资料: