专栏文章

题解：CF1392F Omkar and Landslide

wwmrqwqal & su
CF1392F题解参与者 2已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@mins9c11
此快照首次捕获于
2025/12/02 07:31
3 个月前
此快照最后确认于
2025/12/02 07:31
3 个月前
查看原文

题目链接

CF1392F Omkar and Landslide (*2400)

解题思路

结论题，最终的序列只与 ∑i=1nai\displaystyle \sum_{i=1}^{n} a_i 的值有关。
大致证明就是，首先这个序列是单调不降的，并且，对于任意 i∈[1,n)i \in [1,n)，都有 ai+1−ai≤1a_{i+1}-a_i \le 1，那么容易得出最终序列是个固定值。
那么可以刻画成以下的问题，初始有一个 bb 序列为 [0,1,2,…,n−1][0,1,2,\dots,n-1]，你需要进行 mm 次操作，每次给在满足以下两个的情况下的最左边的数 +1+1：
  • 将这个数 +1+1 后，序列依然单调不降。
  • 将这个数 +1+1 后，序列任意两个数差值不超过 11。
这个贪心是容易做的，总时间复杂度 O(n)O(n)。

参考代码

CPP
ll n,S;
ll a[1000010];
ll b[1000010];
//tulpa
void _clear(){}
void solve()
{
    _clear();
    cin>>n;
    forl(i,1,n)
        cin>>a[i],
        S+=a[i]-i+1,
        b[i]=i-1;
    // cout<<S<<endl;
    ll num=S/n;
    forl(i,1,n)
        b[i]+=num;
    S-=num*n;
    forl(i,1,n)
        if(S)
            b[i]++,
            S--;
    forl(i,1,n)
        cout<<b[i]<<' ';
    cout<<endl;
}

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...