本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-07-10 12:40:53
被这题消耗了 5h 时间，记录一下。
首先，令 $pre_i$ 表示 $\sum\limits_{j=1}^ia_j$，$suf_i$ 表示 $\sum\limits_{j=i}^na_j$，$sum$ 表示 $\sum\limits_{i=1}^na_i$。
首先，考虑无解条件怎么判定。
注意到，每次操作减去的总和必然是偶数。
所以，总和必须是偶数。
最大值不能超过总和的一半。
这是因为，一个数减去 $1$，必然至少有一个其他的数也得同时减去 $1$。
以上两种必然无解，其他情况还不知道。
先把无解情况判掉，再考虑剩余情况怎么处理。
注意到，所有 $n \gt 3$ 的情况都可以转化为 $n=3$ 的情况，且不会转为上述无解情况，可以这样：
从前到后扫描，找到最大的 $x$，满足 $pre_x \le suf_{x+1}$：
此时，可以得到性质 $pre_x \le \frac{sum}{2}$，$suf_{x+2} \le \frac{sum}{2}$。
另外，$x \lt n-1$，否则就是无解情况（之前已经判掉了）。
划分为 $3$ 段，$[1,x],[x+1,x+1],[x+2,n]$：
这 $3$ 段的总和分别相当于新的 $a_1,a_2,a_3$，操作时将它们分别视为一个整体操作就可以了。
接下来，只需要分类讨论 $n=2,3$ 的情况了。
$n=2$ 的情况：
注意到，此时必然满足 $a_1=a_2$，操作一次 $b_1=b_2=a_1$ 就可以了。
$n=3$ 的情况：
如果想要一次操作结束，只能是以下两种情况：
$a_1+a_2 = a_3$。
$a_1=a_2+a_3$。
现在，考虑其他的情况怎么操作。
转化为 $n=2$，且两个数字相等的情况：
变为 $a_1=a_2$ 的情况：
前提条件是 $a_2 - a_1 \le a_3$ 且 $a_2-a_1 \equiv a_3\pmod 2$。
不过，最容易想到的一种条件是 $a_2 - a_3 = a_1$。
变为 $a_2=a_3$ 的情况：
前提条件是 $a_2 - a_3 \le a_1$ 且 $a_2 - a_3 \equiv a_1 \pmod 2$。
最容易想到的条件仍然是 $a_2-a_3=a_1$。
变为 $a_1=a_3$ 的情况：
若 $a_1 \lt a_3$：
那么，操作 $b_2=a_2,b_3=a_3-a_1$。
也就是说，本种情况，能进行转化操作的前提是 $a_3-a_1 = a_2$。
但是，这种情况的答案就是 $1$，使用本转化就得 $2$ 次了，不优。
故，不考虑本情况。
若 $a_1 \ge a_3$：
那么，操作 $b_2 = a_2,b_1 = a_1 - a_3$。
本种情况，转化前提是 $a_1-a_3 = a_2$。
同样，本种情况答案是 $1$，使用本转化就得 $2$ 次了，不优。
故，同样不考虑本情况。
可以看出来，如果转为 $n=2$ 的情况，那么全局一定需要 $2$ 次操作。
变为 $a_1+a_3 = a_2$ 的情况：
此时，尝试求出一个 $d$，使得 $(a_1-d)+(a_3-d)=a_2$。
推导可得，$d = \frac{a_1+a_3-a_2}{2}$。
那么如何证明 $d$ 合法？
$a_1+a_3-a_2 = a_1+a_2+a_3-2a_2$。
由于 $a_1+a_2+a_3$ 为偶数，$a_1+a_3-a_2$ 也是偶数。
所以 $d$ 是整数。
然后需要证明 $d \le \min(a_1,a_3)$。
$a_1 \ge \frac{a_1+a_3-a_2}{2}$ 可以转化为 $2a_1 \ge a_1 + a_3-a_2$，即 $a_1 \ge a_3-a_2$。
如果上述条件不满足，即 $a_1 \lt a_3-a_2$，这就属于无解情况，已经判掉了，不存在。
同样方法也可以证明 $a_3 \ge \frac{a_1+a_3-a_2}{2}$。
由此可以构造出 $b_1=b_3=\frac{a_1+a_3-a_2}{2},b_2=0$。
如果推导到这一步就结束了，那么全局需要 $3$ 次操作。
但实际上，本情况只需要两次操作。
考虑一下 $a_1+a_3=a_2$ 的情况。
下一步转化为 $a_1=a_2$ 的情况，这就需要构造：
$b_1=0,b_2=a_3,b_3=a_3$
注意到，本次转化操作，和下一次转化操作其实可以合并为一次进行操作。
新的构造：
- $b_1=\frac{a_1+a_3-a_2}{2}$。
- $b_2= 0 + (a_3-\frac{a_1+a_3-a_2}{2})$，括号里的数字代表 $a_3$ 第一次操作后的新值。
- $b_3 = \frac{a_1+a_3-a_2}{2} + (a_3-\frac{a_1+a_3-a_2}{2})=a_3$。
这样，一次操作直接转化为了 $a_1=a_2$ 的情况，也就是最终全局 $2$ 次操作。
上述构造，说明了任意非无解情况都只需要最多两次操作。
这是一个比较丑陋的实现：
#include <bits\/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(auto i=(a);i<=(b);i++)
#define REP(i,a,b) for(auto i=(a);i>=(b);i--)
#define FORK(i,a,b,k) for(auto i=(a);i<=(b);i+=(k))
#define REPK(i,a,b,k) for(auto i=(a);i>=(b);i-=(k))
#define pb push_back
#define mkpr make_pair
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
template<class T>
void ckmx(T& a,T b){
a=max(a,b);
}
template<class T>
void ckmn(T& a,T b){
a=min(a,b);
}
template<class T>
T gcd(T a,T b){
return !b?a:gcd(b,a%b);
}
template<class T>
T lcm(T a,T b){
return a\/gcd(a,b)*b;
}
#define gc getchar()
#define eb emplace_back
#define pc putchar
#define ep empty()
#define fi first
#define se second
#define pln pc('\n');
#define islower(ch) (ch>='a'&&ch<='z')
#define isupper(ch) (ch>='A'&&ch<='Z')
#define isalpha(ch) (islower(ch)||isupper(ch))
template<class T>
void wrint(T x){
if(x<0){
x=-x;
pc('-');
}
if(x>=10){
wrint(x\/10);
}
pc(x%10^48);
}
template<class T>
void wrintln(T x){
wrint(x);
pln
}
template<class T>
void read(T& x){
x=0;
int f=1;
char ch=gc;
while(!isdigit(ch)){
if(ch=='-')f=-1;
ch=gc;
}
while(isdigit(ch)){
x=(x<<1)+(x<<3)+(ch^48);
ch=gc;
}
x*=f;
}
void ioopti(){
ios::sync_with_stdio(0);
cin.tie(0);
}
#define NO {puts("-1");return;}
const int maxn=2e5+5;
int n;
ll a[maxn],tot[4];
ll pre[maxn];
ll w(int l,int r){
return pre[r]-pre[l-1];
}
int lef[4],rig[4];\/\/ 记录 a[1],a[2],a[3] 对应原数组实际范围
void op(ll* b,int len){
FOR(id,1,len){\/\/ 目前减去 len 个中的第 id 个
FOR(i,lef[id],rig[id]){
ll _=min(a[i],b[id]);
a[i]-=_;
b[id]-=_;
printf("%lld ",_);
}
}
pln
}
void solve(int id_of_test){
cin>>n;
FOR(i,1,n){
cin>>a[i];
pre[i]=pre[i-1]+a[i];
}
ll sum=pre[n];
if(sum%2)NO
if((*max_element(a+1,a+n+1))>sum\/2)NO
if(n>=4){
FOR(i,1,n){
if(w(1,i)>w(i+1,n)){
lef[1]=1,rig[1]=i-1;
lef[2]=i,rig[2]=i;
lef[3]=i+1,rig[3]=n;
tot[1]=w(1,i-1);
tot[2]=w(i,i);
tot[3]=w(i+1,n);
break;
}
}
}else{
FOR(i,1,n)lef[i]=rig[i]=i,tot[i]=a[i];
}
if(n==2){
puts("1");
ll b[3]={-1,a[1],a[2]};
op(b,2);
}else{
if(tot[1]+tot[2]==tot[3]||tot[1]==tot[2]+tot[3]){
puts("1");
ll b[4]={-1,tot[1],tot[2],tot[3]};
op(b,3);
}else{
puts("2");
ll b[4]={-1,(tot[1]+tot[3]-tot[2])\/2,tot[3]-(tot[1]+tot[3]-tot[2])\/2,tot[3]};
op(b,3);
b[1]=tot[1];
b[2]=tot[2];
b[3]=0;
op(b,3);
}
}
}
int main()
{
int T;
cin>>T;
FOR(_,1,T){
solve(_);
}
return 0;
}
\/*
1. 对题意的理解能否和样例对的上？
2. 每一步操作，能否和自己的想法对应上？
3. 每一步操作的正确性是否有保证？
4. 是否考虑到了所有的 case？特别是极限数据。
5. 变量的数据类型是否与其值域匹配？
6. 时间复杂度有保证吗？
7. 空间多少 MB？
*\/
鲁ICP备2025150228号