题意
题目链接。
给定一个序列
序列的长度范围为
解答
Key 1: 考虑什么情况下,答案等于
发现当
证明:如果对于每个
都有 ,那么对于任何一个 的情况,我们都可以令 全部减去 ,这样最终会形成一个 的形式,容易发现是符合的。然后你可以进行推导,如果 ,则必然有 ,因此也有 ,由逆否命题知,我们只需要 即可。同理可知 也成立。
由对称关系知,其中一者成立,另一者也成立,即
对称关系怎么来的?首先,显然有
,将求和式子中的负项留在左边,正向移到右边,则有 ,故有上述两式等价。
故问题转化为,对于题目给定的
我们发现,若数列中有若干个相同的数
key 2:考虑怎么尽可能快而准确地找到当前数列中最短的合法序列。
我们以
由于子树大小不超过
代码
#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; }
好强
呃呃