【Codeforces 924C】Riverside Curio

题意

【题解】

设第i天总共的线数为t[i]
水平线上线数为m[i]是固定的
水平线下的线数设为d[i]
则d[i]+m[i]+1=t[i]
也就是说问题可以转化为使得t[i]最小
我们可以列出关于t[i]的不等式
t[i]= max{t[i-1],m[i]+1} ···①
t[i]+1>=t[i+1] ,因为每天最多划一条线 ····②
对于①式,直接顺推就好
对于②式
我们用t[i]>=t[i+1]-1逆推
只要t[i]

【代码】

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5;

int n;

int m[N+10],t[N+10],d[N+10];

int main(){

    ios::sync_with_stdio(0),cin.tie(0);

    cin >> n;

    for (int i = 1;i <= n;i++) cin >> m[i];

    for (int i = 1;i <= n;i++){

        t[i] = max(t[i-1],m[i]+1);

    }

    for (int i = n-1;i >= 1;i--){

        //t[i]+1>=t[i+1]

        //t[i]>=t[i+1]-1

        if (t[i]<t[i+1]-1){

            t[i] = t[i+1]-1;

        }

    }

    for (int i = 1;i <= n;i++){

        d[i] = t[i]-m[i]-1;

    }

    long long ans = 0;

    for (int i = 1;i <= n;i++){

        ans = ans + d[i];

    }

    cout<<ans<<endl;

	return 0;

}

巴特西

【Codeforces 924C】Riverside Curio

最新文章

热门文章