D. Shocking Arrangement(cf构造题)

Shocking Arrangement(cf构造题)"/>

D. Shocking Arrangement(cf构造题)

问题 - D - 代码强制 (codeforces)

输入

7
4
3 4 -2 -5
5
2 2 2 -3 -3
8
-3 -3 1 1 1 1 1 1
3
0 1 -1
7
-3 4 3 4 -4 -4 0
1
0
7
-18 13 -18 -17 12 15 13
 

输出

Yes
-5 -2 3 4
Yes
-3 2 -3 2 2
Yes
1 1 1 -3 1 1 1 -3
Yes
-1 0 1
Yes
4 -4 4 -4 0 3 -3
No
Yes
13 12 -18 15 -18 13 -17
 

 给定一段和为0的数组，重新排序使得一段区间的和的绝对值严格小于 原来的最大值和最小值的差（极差）

先将数组排序，如果当前区间和小于0，就放入较大的数，如果大于0,就放入较小的数

#include <iostream>
#include <bits/stdc++.h>
#include <cstring>
#include <vector>
#include <unordered_map>
#include <queue>
#include <set>
#define int long long 
#include <algorithm>
#define x first
#define y second
#define pb emplace_back
#define fu(i,a,b) for(int i=a;i<=b; ++ i)
#define fd(i,a,b) for(int i=a;i>=b;	-- i)
#define endl '\n'
#define ms(x,y) memset(x,y,sizeof x)
#define ios ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
using namespace std;typedef long long LL;
typedef unsigned long long ULL;
typedef vector<vector<LL>> VVL;
typedef vector<vector<int>> VVI;
typedef vector<LL> VL;
typedef vector<int> VI;
typedef vector<string> VS;
typedef pair<int,int> PII;
typedef vector<PII> VPII;
typedef pair<PII,int> PIII;
typedef pair<double,double> PDD;
typedef pair<double,int> PDI;
typedef pair<char,int> PCI;
typedef pair<string,int> PSI;
typedef pair<int,string> PIS;
typedef pair<int,char> PIC;
typedef pair<LL,LL> PLL;
typedef __int128 i128;
typedef unsigned long long ULL;
const int N =1e6 + 10,M = N * 5,base =400  ,INF = 0x3f3f3f3f,P = 131;
const double eps = 1e-8;
const int mod = 998244353;
const LL LNF=(LL) INF * INF;int n;inline void solve()
{cin >> n;VI a(n);fu(i,0,n-1)cin >> a[i];sort(a.begin(),a.end());LL sum=0;if(a == VI(n,0)) {cout <<"No\n";return;}cout <<"Yes\n";int i=0,j=n-1;	VI ans;while(i <= j ){if(sum <= 0) sum+= a[j],ans.push_back(a[j--]);else sum +=a[i],ans.push_back(a[i++]);}for(int i=0;i<n;i ++ )cout << ans[i] <<" \n"[i==n-1];}
signed main()
{
//  freopen("1.txt","r",stdin);#define int long long 
//	init(N-1);ios
//	cout << fixed<<setprecision(2);int t=1;cin>>t;int now = 1;while(t -- ){
//      cout<<"Case "; 
//      cout<<"Case #"; 
//      cout<<"Scenario #"; 
//      cout<< now ++ <<": ";
//      cout<< now ++ <<": \n";solve();}return 0;
}