CF1798D题解

· · 题解

特判一种情况：如果序列全是 0，显然不存在方案。

考虑转化一下左边的式子为前缀和的形式，即 \max_{1\leq l\leq r\leq n}|s_r-s_{l-1}|，等价于前缀和最大值与前缀和最小值之差。

于是得到转化后的条件式：

\max_{i\in [0,n]} s_i-\min_{i\in [0,n]} s_i<\max_{i\in[1,n]} a_i-\min_{i\in[1,n]} a_i

构造时我们只需要令 \max_{i\in [0,n]} s_i\leq\max_{i\in[1,n]} a_i,\min_{i\in [0,n]} s_i\geq\min_{i\in[1,n]} a_i 即可。

从左至右构造答案序列 b，如果当前的前缀和非正，填入一个正数；否则填入一个负数。

代码如下：

#include <bits/stdc++.h>
using namespace std;

const int maxn=3e5+5;
int a[maxn],b[maxn];

void solve()
{
    int n;cin>>n;
    bool flag=0;
    for(int i=1;i<=n;i++) 
    {
        cin>>a[i];
        if(a[i]) flag=1;
    }
    if(!flag) return cout<<"No"<<endl,void();
    int sum=0;
    sort(a+1,a+n+1);
    int l=1,r=n,cnt=0;
    while(l<=r)
    {
        if(sum<=0) sum+=a[r],b[++cnt]=a[r],r--;
        else sum+=a[l],b[++cnt]=a[l],l++;
    }
    cout<<"Yes"<<endl;
    for(int i=1;i<=n;i++) cout<<b[i]<<' ';
    cout<<endl;
}

int main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int t;cin>>t;
    while(t--) solve();
    return 0;
}