CodeChef Starters 83 Division 1 题解
\(\newcommand \v \mathrm\)
\(\text{By DaiRuiChen007}\)
A. Construct String
题目大意
给定长度为 \(n\) 的字符串 \(S\)，每次操作可以把三个相同的字符变成一个同样的字符（\(\texttt {ccc}\to\texttt c\)）
求若干次操作后可以得到最短的 \(S\)
数据范围：\(n\le 10^6\)
思路分析
容易证明贪心地把 \(S\) 中每三个连续的相同字符都操作直到不能操作位置的策略是最优的
用一个栈模拟这个过程即可
时间复杂度 \(\mathcal O(n)\)
代码呈现
#include<bits/stdc++.h>
using namespace std;
inline void solve() {
int n; string s,t;
cin>>n>>s;
for(int i=0;i<n;++i) {
int x=t.length();
if(x<2) t+=s[i];
else if(t[x-1]==s[i]&&t[x-2]==s[i]) t.pop_back();
else t+=s[i];
}
cout<<t<<"\n";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr),cout.tie(nullptr);
int T;
cin>>T;
while(T--) solve();
return 0;
}
B. Order by XOR
题目大意
给三个不同的非负整数数 \(a,b,c\in[0,V]\)，求出某个 \(x\in [0,V]\) 使得 \(a\oplus x<b\oplus x<c\oplus x\)，无解输出 \(-1\)
数据范围：\(V=2^{30}-1\)
思路分析
从高位到低位逐位考虑，对于当前位 \(k\)：
- \(a_k=b_k=c_k\)：\(x_k=0/1\) 均无影响
- \(a_k=b_k\ne c_k\)：贪心可以证明取 \(x_k=b_k\) 更优
- \(a_k\ne b_k=c_k\)：贪心可以证明取 \(x_k=a_k\) 更优
- \(a_k\ne b_k\ne c_k,a_k=c_k\)：
- 若之前所有位 \(a\oplus x,b\oplus x,c\oplus x\) 都相等，则无解
- 若 \(a\oplus x<b\oplus x\) 已被满足，取 \(x_k=b_k\) 即可得到答案
- 若 \(b\oplus x<c\oplus x\) 已被满足，去 \(x_k=a_k\) 即可得到答案
根据上述分类讨论模拟即可
时间复杂度 \(\mathcal O(\log V)\)
代码呈现
#include<bits/stdc++.h>
using namespace std;
inline void solve() {
int a,b,c,ans=0;
scanf("%d%d%d",&a,&b,&c);
auto dig=[&](int x,int k) { return (x>>k)&1; };
int opt=0;
for(int k=30;k>=0;--k) {
int x=dig(a,k),y=dig(b,k),z=dig(c,k);
if(x==y&&y==z) continue;
if(x==y) ans|=y<<k,opt|=1;
if(y==z) ans|=x<<k,opt|=2;
if(x==z) {
if(opt==0) { puts("-1"); return ; }
if(opt==1) ans|=x<<k,opt|=2;
if(opt==2) ans|=y<<k,opt|=1;
}
if(opt==3) { printf("%d\n",ans); return ; }
}
puts("-1");
}
signed main() {
int T;
scanf("%d",&T);
while(T--) solve();
return 0;
}
C. Rotate to Minimum
题目大意
对于一个长度为 \(n\) 的字符串 \(S\) 可以进行如下两种操作：
- 对于某个 \(S_i\) 使 \(S_i\gets S_i+1\)（\(\texttt c\to \texttt d,\texttt z\to \texttt a\)）
- 对于某个 \(S_i\) 是 \(S_i\gets S_i-1\)（\(\texttt d\to \texttt c,\texttt a\to \texttt z\)）
操作 1 不超过 \(p\) 次，操作 2 不超过 \(q\) 次，求最终 \(S\) 最小可能的字典序
数据范围：\(n\le 2\times 10^5\)
思路分析
显然先将 \(S\) 的一段前缀中尽可能多的字符复原成 \(\texttt a\)
再求出最长全 \(\texttt a\) 前缀后的步骤是 trivial 的：全 \(\texttt a\) 前缀的下一个字符用 2 操作最小化字典序，剩下的能用操作 1 变成 \(\texttt a\) 就用，否则不用
考虑二分最大的 \(\texttt a\) 的前缀长度 \(len\)，对于前 \(len\) 个位置，我们需要确定用哪种操作复原，并使得两种操作的总次数分别不超过 \(p,q\)
注意到，当 \(S_i\ne \texttt a\) 时，操作 1 的花费越大，操作 2 的花费越小，反之亦然，因此可以证明最优策略一定是取用操作 1 复原代价最小的若干位置，剩下的选用操作 2，因此一遍排序即可完成判定
然后还有一个细节需要简单贪心处理，因为我们要尽可能最小化 \(S_{len+1}\)，因此在 \(S[1\dots len]\) 的复原中，应尽可能多选用操作 1，剩下按上述过程贪心即可
时间复杂度 \(\mathcal O(n\log^2n)\)
代码呈现
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+1;
char str[MAXN];
inline void solve() {
int n,u,d;
scanf("%d%d%d%s",&n,&u,&d,str+1);
int l=1,r=n,res=0;
while(l<=r) {
auto check=[&](int x) -> bool {
vector <pair<int,int>> v;
for(int i=1;i<=x;++i) v.push_back(make_pair((26-(str[i]-'a'))%26,str[i]-'a'));
int p=0,q=0;
sort(v.begin(),v.end());
for(auto t:v) {
if(t.first+p<=u) p+=t.first;
else q+=t.second;
}
return p<=u&&q<=d;
};
int mid=(l+r)>>1;
if(check(mid)) res=mid,l=mid+1;
else r=mid-1;
}
vector <pair<int,int>> v;
for(int i=1;i<=res;++i) {
v.push_back(make_pair((26-(str[i]-'a'))%26,str[i]-'a'));
str[i]='a';
}
sort(v.begin(),v.end());
for(auto t:v) {
if(t.first<=u) u-=t.first;
else d-=t.second;
}
if(res<n) str[res+1]-=d;
for(int i=res+2;i<=n;++i) {
int x=(26-(str[i]-'a'))%26;
if(u>=x) str[i]='a',u-=x;
}
printf("%s\n",str+1);
}
signed main() {
int T;
scanf("%d",&T);
while(T--) solve();
return 0;
}
D. Saber Slays
题目大意
你需要进行若干次“挑战”，设你的能力值为 \(u\)，对手的能力值为 \(v\)，那么每次“挑战”会发生如下 \(3\) 种结果之一：
- \(u<v\)：你失败
- \(u=v\)：你胜利，且 \(u\gets u-1\)
- \(u>v\)：你胜利
给定 \(n\) 个对手，第 \(i\) 个对手的能力值为 \(s_i\)，\(q\) 次询问 \(l,r\)，你需要回答如果你想依次战胜编号为 \(l,l+1,\dots ,r\) 的对手，你的初始能力值至少是多少
数据范围：\(n,q\le 5\times 10^5\)
思路分析
考虑用线段树维护每个区间对应的信息 \((\v{in},\v{out})\)，表示想要战胜这个区间中的所有人，初始能力值至少是 \(\v{in}\)，且最终你的能力值会变成 \(\v{out}\)，一个显然的观察是对于某个区间 \([l,r]\)，其 \(\v{in}\in\{\max[s_l\sim s_r],\max[s_l\sim s_r]+1\}\)
考虑合并左右区间信息 \((L_\v{in},L_\v{out}),(R_\v{in},R_\v{out})\) 的过程
- 若 \(L_\v{out}>R_\v{in}\)：此时直接从 \(L_\v{in}\) 进入，得到 \(L_\v{out}\) 后在右区间一定有 \(L_\v{out}>R_\max\)，因此最终的结果是 \((L_\v{in},L_\v{out})\)
- 若 \(L_{\v out}=R_\v{in}\)：此时直接从 \(L_\v{in}\) 进入，得到 \(L_\v{out}=R_\v{in}\) 恰好可以通过右区间并得到 \(R_\v{out}\)，因此最终的结果是 \((L_\v{in},R_\v{out})\)
- 若 \(L_\v{out}<R_\v{in}\)：
- 若 \(R_\v{in}>L_\v{in}\)，此时直接用 \(R_\v{in}\) 进入，在左区间一定有 \(L_\max<R_\v{in}\)，可以直接到右区间，因此最终的结果是 \((R_\v{in},R_\v{out})\)
- 否则说明 \(L_\v{in}=L_\max=(L+R)_{\max}\)，此时 \(L_\v{in}\) 无法通过，选择用 \(L_\v{in}+1\) 进入，最终的结果是 \((L_\v{in}+1,L_\v{in}+1)\)
用线段树维护上述信息的合并即可
时间复杂度 \(\mathcal O((n+q)\log n)\)
代码呈现
#include<bits/stdc++.h>
using namespace std;
const int MAXN=5e5+1,INF=2e9;
struct Data {
int in,out;
Data(): in(INF),out(INF) {}
Data(int x): in(x),out(x-1) {}
Data(int _i,int _o): in(_i),out(_o) {}
inline friend Data operator +(const Data &L,const Data &R) {
if(L.out>R.in) return Data(L.in,L.out);
else if(L.out==R.in) return Data(L.in,R.out);
else {
if(L.in<R.in) return Data(R.in,R.out);
else return Data(L.in+1,L.in+1);
}
}
};
int n,q,a[MAXN];
class SegmentTree {
private:
struct Node {
Data data;
} tree[MAXN<<2];
inline int left(int x) { return x<<1; }
inline int right(int x) { return x<<1|1; }
inline void pushup(int pos) {
tree[pos].data=tree[left(pos)].data+tree[right(pos)].data;
}
public:
inline void Build(int l=1,int r=n,int pos=1) {
if(l==r) { tree[pos].data=Data(a[l]); return ; }
int mid=(l+r)>>1;
Build(l,mid,left(pos));
Build(mid+1,r,right(pos));
pushup(pos);
}
inline Data Query(int ul,int ur,int l=1,int r=n,int pos=1) {
if(ul<=l&&r<=ur) return tree[pos].data;
int mid=(l+r)>>1;
if(ur<=mid) return Query(ul,ur,l,mid,left(pos));
if(mid<ul) return Query(ul,ur,mid+1,r,right(pos));
return Query(ul,ur,l,mid,left(pos))+Query(ul,ur,mid+1,r,right(pos));
}
} S;
inline void solve() {
scanf("%d%d",&n,&q);
for(int i=1;i<=n;++i) scanf("%d",&a[i]);
S.Build();
while(q--) {
int l,r;
scanf("%d%d",&l,&r);
printf("%d\n",S.Query(l,r).in);
}
}
signed main() {
int T;
scanf("%d",&T);
while(T--) solve();
return 0;
}
E. Restoration
题目大意
交互器有一个大小为 \(n\) 的排列 \(p_i\)，每次交互你可以询问一个大小为 \(n\) 的排列，交互器会返回排列 \(r_i=p_{q_i}\) 中所有Local Max（前缀最大值）的位置（即所有满足 \(\forall 1\le j<i\) 均有 \(r_j<r_i\) 的 \(i\)）
你需要在 \(n-1\) 次询问内还原排列 \(p_i\)
数据范围：\(n\le 500\)
思路分析
考虑从排列的 Local Max 入手，注意到最后一个 Local Max 一定是 \(n\)，因此不管我们第一次询问的 \(q\) 是什么，我们总能确定 \(n\) 的位置
接下来考虑 \(n-1\) 的位置，用类似的方法找倒数二个 Local Max，为了保证 \(n-1\) 不被 \(n\) 挡住，我们可以通过选择合适的 \(q\) 使得 \(r_n=n\)，然后找倒数第二个 Local Max 即可，同理可以以一次询问的代价分别确定 \(n-2,n-3,\dots ,1\) 的对应位置
注意到当已经确定 \(2\sim n\) 的位置时，\(1\) 的位置也可以求出，因此可以做到 \(n-1\) 次询问还原 \(p_i\)
时间复杂度 \(\mathcal O(n^2)\)
代码呈现
#include<bits/stdc++.h>
using namespace std;
inline void solve() {
int n;
cin>>n;
vector <int> p(n+1),idx(n+1);
for(int i=n;i>1;--i) {
vector <int> q(n+1,0),vis(n+1,0);
for(int j=i+1;j<=n;++j) q[j]=idx[j],vis[q[j]]=1;
for(int j=1;j<=i;++j) {
for(int k=q[j-1]+1;k<=n;++k) if(!vis[k]) { q[j]=k,vis[k]=true; break; }
}
cout<<"? ";
for(int j=1;j<=n;++j) cout<<q[j]<<" ";
cout<<endl;
int s; cin>>s; vector <int> v(s);
for(int j=0;j<s;++j) cin>>v[j];
for(int j=0;j<s;++j) {
if(v[j]<=i) idx[i]=q[v[j]];
}
p[idx[i]]=i;
}
for(int i=1;i<=n;++i) if(!p[i]) p[i]=1;
cout<<"! ";
for(int i=1;i<=n;++i) cout<<p[i]<<" ";
cout<<endl;
int ans; cin>>ans;
}
signed main() {
int T;
cin>>T;
while(T--) solve();
return 0;
}
F. Mex Segments
题目大意
给定一个 \(0\sim n-1\) 的排列 \(a_i\)，\(q\) 次询问，每次询问给定 \(l,r,s,t\)，你需要回答有多少 \(1\le x\le y\le n\) 使得 \(l\le y-x+1\le r\) 且 \(s\le\v{mex}(a_x,a_{x+1},\dots,a_y)\le t\)
数据范围：\(n,q\le 10^6\)
思路分析
考虑当我们强制选择了 \(0\sim k-1\) 号元素，此时对 \(x,y\) 的限制形如 \(x\le u\le v\le y\)，那么我们可以得到有多少区间 \([x,y]\) 满足 \(\v{mex}(a_x,a_{x+1},\dots,a_y)\ge k\)，因此考虑用后缀和把答案拆成 \(\v{mex}(a_x,a_{x+1},\dots,a_y)\ge s\) 和 \(\v{mex}(a_x,a_{x+1},\dots,a_y)\ge t+1\) 两个询问
离线后我们每次加入 \(k\) 所在的位置，更新对应的 \([u,v]\)，然后再对区间长度用前缀和拆分，长度 \(\le x\) 的区间共有 \(\sum_{i=v-u+1}^x \min(u,n-x+1)-\max(v-x+1,1)+1\) 个，分别分类讨论拆开 \(\min\) 和 \(\max\) 即可
时间复杂度 \(\mathcal O(n+q)\)
代码呈现
#include<bits/stdc++.h>
#define int long long
using namespace std;
struct Query {
int l,r,id,c;
Query(int _l=0,int _r=0,int _id=0,int _c=0): l(_l),r(_r),id(_id),c(_c) {}
};
inline void solve() {
int n,q;
scanf("%lld%lld",&n,&q);
vector <int> a(n+1),pos(n+1),ans(q+1);
vector <vector<Query>> Q(n+1);
for(int i=1;i<=n;++i) scanf("%lld",&a[i]),pos[a[i]]=i;
auto sum=[&](int l,int r) { return (l+r)*(r-l+1)/2; };
for(int i=1;i<=q;++i) {
int l,r,lo,hi;
scanf("%lld%lld%lld%lld",&l,&r,&lo,&hi);
if(lo>0) Q[lo-1].push_back(Query(l,r,i,1));
else ans[i]+=sum(n-r+1,n-l+1);
if(hi<n) Q[hi].push_back(Query(l,r,i,-1));
}
int lb=pos[0],rb=pos[0];
for(int i=0;i<n;++i) {
lb=min(lb,pos[i]),rb=max(rb,pos[i]);
int len=rb-lb+1;
auto calc=[&](int x) -> int {
if(x<rb-lb+1) return 0;
int ans=x-len+1;
if(x<=n-lb+1) ans+=lb*(x-len+1);
else ans+=lb*(n-rb+1)+sum(n-x+1,lb-1);
if(x<=rb) ans-=sum(rb-x+1,lb);
else ans-=sum(1,lb)+(x-rb);
return ans;
};
for(auto x:Q[i]) {
ans[x.id]+=x.c*(calc(x.r)-calc(x.l-1));
}
}
for(int i=1;i<=q;++i) printf("%lld\n",ans[i]);
}
signed main() {
int T;
scanf("%lld",&T);
while(T--) solve();
return 0;
}
G. Beauty Sum
题目大意
给定一棵大小为 \(n\) 的树，点有点权 \(a_i\)，记 \(\v{path}(u,v)\) 为树上 \(u\to v\) 的简单路径所经过的节点集合
求 \(\sum_{1\le u<v\le n}\min\{a_i\mid i\in\v{path}(u,v\}\times\max\{a_i\mid i\in\v{path}(u,v)\}\)，即所有路径 \(u\to v\) 上最大值与最小值乘积的和
数据范围：\(n\le 2\times 10^5\)
思路分析
考虑点分治，设 \(x_i,y_i\) 分别表示节点 \(i\) 到当前分支中心 \(\v{root}\) 路径上的最小值和最大值，那么此时经过 \(\v{root}\) 的路径对答案的贡献就是 \(\sum_{u,v}[\v{subtree}(u)\ne \v{subtree}(v)]\times \min(x_u,x_v)\times\max(y_u,y_v)\)（\(\v{subtree}(u)\) 表示 \(u\) 在 \(\v{root}\) 的哪棵子树中）
但是这个式子实际上是在对三元组 \((\v{subtree}(u),x_u,y_u)\) 求三维偏序，直接求是 \(\mathcal O(n\log^2n)\) 的，加上点分治后复杂度达到 \(\mathcal O(n\log^3n)\)，无法通过此题
考虑我们在点分树统计答案时所用的容斥技巧，将 \(\v{root}\) 对答案的贡献重新表示成 \(\sum_{u,v}\min(x_u,x_v)\times\max(y_u,y_v)-\sum_{u,v}[\v{subtree}(u)= \v{subtree}(v)]\times \min(x_u,x_v)\times\max(y_u,y_v)\)
注意到第二个式子只需要对每个子树中分别求出 \(\sum_{u,v}\min(x_u,x_v)\times\max(y_u,y_v)\) 即可，而这个式子可以看成 \((x_u,y_u)\) 的二维偏序问题，用 CDQ 分治套双指针即可在 \(\mathcal O(n\log n)\) 的时间复杂度内解决（也可以使用平衡树或树状数组维护点的坐标，复杂度相同）
时间复杂度 \(\mathcal O(n\log^2n)\)
代码呈现
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=2e5+1,MOD=1e9+7;
vector <int> G[MAXN];
int ans=0;
int a[MAXN],siz[MAXN],cur[MAXN];
int mindis[MAXN],maxdis[MAXN];
bool vis[MAXN];
struct Point {
int x,y;
Point(int _x=0,int _y=0): x(_x),y(_y) {}
} P[MAXN];
int pre[MAXN],suf[MAXN];
inline void calc(int p) {
auto solve=[&](const vector <int> &ver) -> int {
int n=ver.size(),ans=0;
for(int i=1;i<=n;++i) P[i]=Point(mindis[ver[i-1]],maxdis[ver[i-1]]);
sort(P+1,P+n+1,[](Point u,Point v){ return u.x<v.x; });
auto CDQ=[&](auto self,int l,int r) -> void {
if(l==r) return ;
int mid=(l+r)>>1;
self(self,l,mid),self(self,mid+1,r);
pre[l]=P[l].x%MOD; //prefix-sum of x
for(int i=l+1;i<=mid;++i) pre[i]=(pre[i-1]+P[i].x)%MOD;
suf[mid]=P[mid].x*P[mid].y%MOD; //suffix-sum of x*y
for(int i=mid-1;i>=l;--i) suf[i]=(suf[i+1]+P[i].x*P[i].y%MOD)%MOD;
pre[mid+1]=1; //prefix-sum of 1
for(int i=mid+2;i<=r;++i) pre[i]=(pre[i-1]+1)%MOD;
suf[r]=P[r].y; //suffix-sum of y
for(int i=r-1;i>=mid+1;--i) suf[i]=(suf[i+1]+P[i].y)%MOD;
for(int lp=l,rp=mid;lp<=mid;++lp) {
while(rp<r&&P[rp+1].y<=P[lp].y) ++rp;
if(mid+1<=rp) ans=(ans+P[lp].x*P[lp].y%MOD*pre[rp]%MOD)%MOD;
if(rp+1<=r) ans=(ans+P[lp].x*suf[rp+1]%MOD)%MOD;
}
for(int rp=mid+1,lp=l-1;rp<=r;++rp) {
while(lp<mid&&P[lp+1].y<=P[rp].y) ++lp;
if(l<=lp) ans=(ans+P[rp].y*pre[lp]%MOD)%MOD;
if(lp+1<=mid) ans=(ans+suf[lp+1])%MOD;
}
inplace_merge(P+l,P+mid+1,P+r+1,[](Point u,Point v){ return u.y<v.y; });
};
CDQ(CDQ,1,n);
return ans;
};
mindis[p]=maxdis[p]=a[p];
vector <int> ver{p};
for(int v:G[p]) {
if(vis[v]) continue;
vector <int> subt;
auto dfs=[&](auto self,int p,int fa) -> void {
ver.push_back(p),subt.push_back(p);
mindis[p]=min(mindis[fa],a[p]);
maxdis[p]=max(maxdis[fa],a[p]);
for(int v:G[p]) {
if(vis[v]||v==fa) continue;
self(self,v,p);
}
};
dfs(dfs,v,p);
ans=(ans+MOD-solve(subt))%MOD;
}
ans=(ans+solve(ver))%MOD;
}
inline void dfs(int p) {
calc(p); vis[p]=true;
for(int v:G[p]) {
if(vis[v]) continue;
int tot=siz[v],rt=0;
auto get=[&](auto self,int p,int fa) -> void {
cur[p]=0,siz[p]=1;
for(int v:G[p]) {
if(vis[v]||v==fa) continue;
self(self,v,p);
cur[p]=max(cur[p],siz[v]);
siz[p]+=siz[v];
}
cur[p]=max(cur[p],tot-siz[p]);
if(!rt||cur[p]<cur[rt]) rt=p;
};
get(get,v,p);
dfs(rt);
}
}
inline void solve() {
int n;
scanf("%lld",&n);
for(int i=1;i<=n;++i) scanf("%lld",&a[i]),vis[i]=false,G[i].clear();
ans=0;
for(int i=1;i<n;++i) {
int u,v;
scanf("%lld%lld",&u,&v);
G[u].push_back(v);
G[v].push_back(u);
}
int tot=n,rt=0;
auto get=[&](auto self,int p,int fa) -> void {
cur[p]=0,siz[p]=1;
for(int v:G[p]) {
if(vis[v]||v==fa) continue;
self(self,v,p);
cur[p]=max(cur[p],siz[v]);
siz[p]+=siz[v];
}
cur[p]=max(cur[p],tot-siz[p]);
if(!rt||cur[p]<cur[rt]) rt=p;
};
get(get,1,0);
dfs(rt);
printf("%lld\n",(MOD+1)/2*ans%MOD);
}
signed main() {
int T;
scanf("%lld",&T);
while(T--) solve();
return 0;
}
H. The Faulty Tree
题目大意
给 \(n\) 个权值 \(w_1,w_2,\dots,w_n\)，A 和 B 分别构造一棵二叉树，以 \(1\sim n\) 为叶子并最小化 \(\sum_{i=1}^n w_i\times dep_i\)
其中 A 的二叉树上的每个节点都有 \(\ge 1\) 个儿子是叶子，现在 B 想要使他构造的二叉树的权值严格小于 A 构造的二叉树的权值，求出 A 至少要修改几个 \(w_i\) 的值，并给出方案（无 解输出 \(-1\)）
数据范围： \(n\le 10^6\)
思路分析
注意到 \(n\le 3\) 时两个人构造的树一定同构，因此直接输出
显然 A 会把叶子按权值从小到大，从深到浅排序
考虑在 A 构造的二叉树的基础上进行某种调整操作使得新树的权值更小
显然考虑对二叉树进行 zig-zag 操作，如下图：
注意 \(A,B\) 是节点的权值，\(C\) 是子树的权值和，那么此时树的权值会加上 \(A-C\)
考虑回到序列上，假设 \(w_i\) 按升序排列，其前缀和记为 \(sum_i\)，那么序列 \(w\) 可以使 B 获胜当且仅当存在一个 \(3< i\le n\) 使得 \(w_i<sum_{i-2}\)，若这样的 \(i\) 已经存在，答案为 \(0\)，可以直接输出，而劣的做法一定是使得 \(w_i=w_{i-1}=w_{i-2}\)，此时 \(sum_{i-2}=sum_{i-3}+w_{i-2}=w_{i}+sum_{i-3}>w_i\)，因此答案至多为 \(2\)
考虑答案为 \(1\) 的情况，显然只有可能最小化 \(w_i\) 或最大化 \(sum_{i-2}\)，第一种情况尝试令 \(w_i\gets w_{i-1}\)，第二种情况尝试另 \(w_1\gets w_{i-1}\)，分别判断即可
容易证明不存在其他的策略
时间复杂度 \(\mathcal O(n\log n)\)
代码呈现
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=1e6+1;
int a[MAXN],sum[MAXN],p[MAXN],q[MAXN];
inline void solve() {
int n;
scanf("%lld",&n);
for(int i=1;i<=n;++i) scanf("%lld",&a[i]),p[i]=i;
sort(p+1,p+n+1,[&](int x,int y){ return a[x]<a[y]; });
for(int i=1;i<=n;++i) q[p[i]]=i;
sort(a+1,a+n+1);
if(n<=3) { puts("NO"); return ; }
puts("YES");
for(int i=1;i<=n;++i) sum[i]=sum[i-1]+a[i];
auto print=[&]() { for(int i=1;i<=n;++i) printf("%lld ",a[q[i]]); puts(""); };
for(int i=3;i<=n;++i) if(sum[i-2]>a[i]) { print(); return ; }
for(int i=3;i<=n;++i) if(sum[i-2]>a[i-1]) { a[i]=a[i-1],print(); return ; }
for(int i=3;i<=n;++i) if(sum[i-2]-a[1]+a[i-1]>a[i]) { a[1]=a[i-1],print(); return ; }
a[n]=a[n-1]=a[n-2],print();
}
signed main() {
int T;
scanf("%lld",&T);
while(T--) solve();
return 0;
}
