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

题意

题目链接

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

序列的长度范围为 1n106

解答

Key 1: 考虑什么情况下,答案等于 i=1nyi

发现当 y1i=1n1max(0,yiyi+1)yni=1n1max(0,yi+1yi)​ 时符合。

证明:如果对于每个 k 都有 yki=kn1max(0,yiyi+1),那么对于任何一个 yi>yi+1 的情况,我们都可以令 y1yi 全部减去 yiyi+1 ,这样最终会形成一个 y1=y2==ykyk+1==yn 的形式,容易发现是符合的。然后你可以进行推导,如果 yk<i=kn1max(0,yiyi+1),则必然有 yk1<i=k1n1max(0,yiyi+1),因此也有 y1<i=1n1max(0,yiyi+1),由逆否命题知,我们只需要 y1i=1n1max(0,yiyi+1) 即可。同理可知 yni=1n1max(0,yi+1yi) 也成立。

由对称关系知,其中一者成立,另一者也成立,即 y1+yni=1n1|yiyi+1| 时,有答案等于 i=1nyi​。

对称关系怎么来的?首先,显然有 y1+i=1k1(yi+1yi)=yn,将求和式子中的负项留在左边,正向移到右边,则有 y1i=1n1max(0,yiyi+1)=yni=1n1max(0,yi+1yi),故有上述两式等价。

故问题转化为,对于题目给定的 yi 数列,我们可以令其中的某些 yi 加上某些数,形成一个新的数列 xixi 的和即为答案,那么我们要做的就是使这些加的数尽可能少。不妨记 M=y1+ynsumi=1n1|yiyi+1|,我们要使得 M0

我们发现,若数列中有若干个相同的数 yl=yl+1==yr,如果有 yl1ylyr+1yr=yl,那么我们让 ylyr 全部加上 1,就可以使得 M 加上 2,而这一操作的代价是 rl+1。显然,我们希望找到尽可能短的 ylyr​ 序列满足上述条件。

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

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

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

代码

#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
    2024-4-17
    2024-4-17 15:34:39

    好强

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

      呃呃

发送评论 编辑评论

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