题解归档 - cf104114N

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf104114N
• 本地来源：problems/cf104114N/idea.md
• 题目链接：https://codeforces.com/gym/104114/problem/N
• 原始标题：cf104114N - Nusret Gökçe

思路

cf104114N - Nusret Gökçe

We need t[i] >= s[i], |t[i]-t[i+1]| <= m, and minimum total sum.

Every original value s[j] imposes a lower bound on every position:

t[i] >= s[j] - m * |i-j|.

Therefore the component-wise minimal feasible array is

t[i] = max_j (s[j] - m * |i-j|).

This array is feasible because it is the maximum of functions with slope bounded by m, hence it is also m-Lipschitz. Compute it with two sweeps:

• left contribution: max_{j<=i}(s[j]+m*j)-m*i;
• right contribution: max_{j>=i}(s[j]-m*j)+m*i.

Complexity: O(n).

代码

来源：problems/cf104114N/solution.cpp

#include<bits/stdc++.h>
using namespace std;
using ll=long long;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    ll m;
    cin>>n>>m;
    vector<ll>s(n),ans(n);
    for(ll &x:s) cin>>x;

    const ll NEG=-(1LL<<62);
    ll best=NEG;
    for(int i=0;i<n;i++){
        best=max(best,s[i]+m*i);
        ans[i]=best-m*i;
    }
    best=NEG;
    for(int i=n-1;i>=0;i--){
        best=max(best,s[i]-m*i);
        ans[i]=max(ans[i],best+m*i);
    }

    for(int i=0;i<n;i++){
        if(i) cout<<" ";
        cout<<ans[i];
    }
    cout<<"\n";
    return 0;
}