2024 CCPC Final Chengdu (第九届 CCPC 总决赛): A 题 – Add One 2 题解

题意

题目链接

给定一个序列 $y$​, 初始有一个全零序列 $x$​。每次可以选择一个长度为 $k$​ 的前缀或者一个长度为 $k$​ 的后缀将其加一,代价是 $k$​。问最少需要多少代价能使得对于所有 $i$​ 都满足 $b_i\geq a_i$​。

序列的长度范围为 $1 \le n \le 10^6$。

解答

Key 1: 考虑什么情况下,答案等于 $\sum_{i=1}^{n} y_i$。

发现当 $y_1 \ge \sum_{i=1}^{n-1} \max(0,y_i-y_{i+1})$ 或 $y_n \ge \sum_{i=1}^{n-1} \max(0,y_{i+1}-y_i)$​ 时符合。

证明:如果对于每个 $k$ 都有 $y_k \ge \sum_{i=k}^{n-1} \max(0,y_i-y_{i+1})$,那么对于任何一个 $y_i > y_{i+1}$ 的情况,我们都可以令 $y_1 \sim y_i$ 全部减去 $y_{i}-y_{i+1}$ ,这样最终会形成一个 $y_1 = y_2 =\dots = y_k \neq y_k+1 = \dots =y_n$ 的形式,容易发现是符合的。然后你可以进行推导,如果 $y_k < \sum_{i=k}^{n-1} \max(0,y_i-y_{i+1})$,则必然有 $y_1 < \sum_{i=k-1}^{n-1} \max(0,y_i-y_{i+1})$,因此也有 $y_1 < \sum_{i=1}^{n-1} \max(0,y_i-y_{i+1})$,由逆否命题知,我们只需要 $y_1 \ge \sum_{i=1}^{n-1} \max(0,y_i-y_{i+1})$ 即可。同理可知 $y_n \ge \sum_{i=1}^{n-1} \max(0,y_{i+1}-y_i)$ 也成立。

由对称关系知,其中一者成立,另一者也成立,即 $y_1+y_n \ge \sum_{i=1}^{n-1}|y_i-y_{i+1}|$ 时,有答案等于 $\sum_{i=1}^{n} y_i$​。

对称关系怎么来的?首先,显然有 $y_1+\sum_{i=1}^{k-1}(y_{i+1}-y_{i})=y_n$,将求和式子中的负项留在左边,正向移到右边,则有 $y_1-\sum_{i=1}^{n-1} \max(0,y_i-y_{i+1})=y_n – \sum_{i=1}^{n-1} \max(0,y_{i+1}-y_i)$,故有上述两式等价。

故问题转化为,对于题目给定的 $y_i$ 数列,我们可以令其中的某些 $y_i$ 加上某些数,形成一个新的数列 $x_i$,$x_i$ 的和即为答案,那么我们要做的就是使这些加的数尽可能少。不妨记 $M=y_1+y_n -sum_{i=1}^{n-1}|y_i-y_{i+1}|$,我们要使得 $M \ge 0$。

我们发现,若数列中有若干个相同的数 $y_l=y_{l+1} =\dots =y_r$,如果有 $y_{l-1} \ge y_l$ 且 $y_r+1 \ge y_r=y_l$,那么我们让 $y_l \sim y_r$ 全部加上 $1$,就可以使得 $M$ 加上 $2$,而这一操作的代价是 $r-l+1$。显然,我们希望找到尽可能短的 $y_l \sim y_r$​ 序列满足上述条件。

key 2:考虑怎么尽可能快而准确地找到当前数列中最短的合法序列。

我们以 $y_i$ 为权值,建立一棵大根堆的笛卡尔树,可以发现,对于每一个点,对其操作时的长度就是以其为根的子树的大小,其可以加的最大数值就是其与其父亲节点的差值。然后,我们按照子树大小从小到大遍历所有点并更新 $M$ 和答案,直至 $M \ge 0$​ 时结束遍历。

由于子树大小不超过 $n$,可以用桶排做到 $O(n)$ 的时间复杂度。也可直接 sort,时间复杂度为 $O(n\log n)$,足够通过。

代码

#include<bits/stdc++.h>
#define ll long long
#define pi pair<int,int>
#define fi first
#define se second
#define mk make_pair
#define pb push_back
#define int long long
using namespace std;
const int N=1e6+5;
int ls[N],rs[N],fa[N];
int T,n,y[N];
struct node{
    int siz,pos;
}a[N];
void dfs(int u,int f){
    if(u==0) return;
    fa[u]=f;a[u].siz=1;
    dfs(ls[u],u);dfs(rs[u],u);
    a[u].siz+=a[ls[u]].siz;a[u].siz+=a[rs[u]].siz;
    a[u].pos=u;
}
bool cmp(node i,node j){
    return i.siz<j.siz;
}
void solve(){
    scanf("%lld",&n);
    ll ans=0,now=0,M=0;
    for(int i=1;i<=n;i++) fa[i]=ls[i]=rs[i]=0;
    for(int i=1;i<=n;i++){
        scanf("%lld",&y[i]);
        ans+=y[i];
        if(i!=1) now+=abs(y[i]-y[i-1]);
    }
    M=y[1]+y[n];
    stack<int> st;
    for(int i=1;i<=n;i++){
        while(!st.empty()&&y[i]>y[st.top()]){ls[i]=st.top();st.pop();}
        if(!st.empty()) rs[st.top()]=i;
        st.push(i);
    }
    int root=0;
    while(!st.empty()){root=st.top();st.pop();}
    dfs(root,0);
    sort(a+1,a+1+n,cmp);
    for(int u=1;u<=n&&M<now;u++){
        if((now-M)<=2*(y[fa[a[u].pos]]-y[a[u].pos])){
            ans+=(now-M)/2*a[u].siz;
            now-=(now-M);
        }
        else{
            now-=2*(y[fa[a[u].pos]]-y[a[u].pos]);
            ans+=(y[fa[a[u].pos]]-y[a[u].pos])*a[u].siz;    
        }
    }
    printf("%lld\n",ans);
}
signed main(){
    scanf("%lld",&T);
    while(T--) solve();
    return 0;
}
本文作者:water_tomato

评论

  1. a999999
    1 月前
    2024-4-17 15:34:39

    好强

    • 博主
      a999999
      1 月前
      2024-4-23 10:45:14

      呃呃

发送评论 编辑评论

|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇