网硕互联帮助中心小苯的数组构造
时间限制：1 秒 空间限制：256M
网页链接
牛客tracker
牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！ 
题目描述
大白熊给了小苯一个长度为
n
n
n 的数组
a
a
a，他希望小苯将数组
a
a
a 变成有序（非递减）的。具体的，小苯需要进行如下操作：
b
b
b，长度也为
n
n
n，且元素满足：
−
10
10
≤
b
i
≤
10
10
-10^{10} \\le b_i \\le 10^{10}
−1010≤bi≤1010。
1
≤
i
≤
n
1 \\le i \\le n
1≤i≤n，都执行
a
i
=
a
i
+
b
i
a_i = a_i + b_i
ai=ai+bi。
大白熊希望在执行完操作后
a
a
a 数组满足有序，同时要最小化数组
b
b
b 的极差，即使得：
max
(
b
1
,
b
2
,
…
,
b
n
)
−
min
(
b
1
,
b
2
,
…
,
b
n
)
\\max(b_1, b_2, \\dots, b_n) – \\min(b_1, b_2, \\dots, b_n)
max(b1,b2,…,bn)−min(b1,b2,…,bn)
最小。
请你帮小苯找出一个合法的
b
b
b 数组吧。
注：如有多解输出任意即可。
输入描述
输入包含两行。
- 第一行一个正整数
n
(
1
≤
n
≤
2
×
10
5
)
n\\ (1 \\le n \\le 2 \\times 10^5)
n (1≤n≤2×105)，表示a
a
a 的长度。 - 第二行
n
n
n 个整数a
i
(
−
10
9
≤
a
i
≤
10
9
)
a_i\\ (-10^9 \\le a_i \\le 10^9)
ai (−109≤ai≤109)，表示数组a
a
a 的元素。
输出描述
输出包含一行
n
n
n 个整数，表示构造出的
b
b
b 数组（有多解输出任意即可）。
如果找不到合法的
b
b
b 数组，请输出一个整数
−
1
-1
−1。
示例 1
输入：
2
1 2
输出：
114514 114514
说明： 可以构造
b
=
[
114514
,
114514
]
b = [114514, 114514]
b=[114514,114514]，这样
b
b
b 的极差为
0
0
0，可以证明不存在比
0
0
0 更小的极差。
备注
数组的极差 = 数组中的最大值减去最小值。
数据范围与提示
-
1
≤
n
≤
2
×
10
5
1 \\le n \\le 2 \\times 10^5
1≤n≤2×105 -
−
10
9
≤
a
i
≤
10
9
-10^9 \\le a_i \\le 10^9
−109≤ai≤109 -
−
10
10
≤
b
i
≤
10
10
-10^{10} \\le b_i \\le 10^{10}
−1010≤bi≤1010 - 核心思路：
- 记最终序列
f
i
=
a
i
+
b
i
f_i = a_i + b_i
fi=ai+bi，要求f
f
f 非递减。b
b
b 的极差等价于max
i
(
f
i
−
a
i
)
−
min
i
(
f
i
−
a
i
)
\\max_i(f_i – a_i) – \\min_i(f_i – a_i)
maxi(fi−ai)−mini(fi−ai)，要让它最小。 - 两种自然的构造可分别给出上界：
- 取
b
i
=
p
m
x
i
−
a
i
b_i = \\mathrm{pmx}_i – a_i
bi=pmxi−ai（p
m
x
i
\\mathrm{pmx}_i
pmxi 为前缀最大值），此时f
i
=
p
m
x
i
f_i = \\mathrm{pmx}_i
fi=pmxi 非递减，b
b
b 的极差为max
i
(
p
m
x
i
−
a
i
)
\\max_i(\\mathrm{pmx}_i – a_i)
maxi(pmxi−ai)； - 取
b
i
=
s
m
n
i
−
a
i
b_i = \\mathrm{smn}_i – a_i
bi=smni−ai（s
m
n
i
\\mathrm{smn}_i
smni 为后缀最小值），此时f
i
=
s
m
n
i
f_i = \\mathrm{smn}_i
fi=smni 非递减，b
b
b 的极差为max
i
(
a
i
−
s
m
n
i
)
\\max_i(a_i – \\mathrm{smn}_i)
maxi(ai−smni)。
- 取
- 最优极差为
D
=
min
{
max
i
(
p
m
x
i
−
a
i
)
,
max
i
(
a
i
−
s
m
n
i
)
}
D = \\min\\left\\{ \\max_i(\\mathrm{pmx}_i – a_i),\\ \\max_i(a_i – \\mathrm{smn}_i) \\right\\}
D=min{imax(pmxi−ai), imax(ai−smni)} 选择上述两种构造中更优的一种输出即可（也可以在此基础上统一平移，使得所有b
i
b_i
bi 都落在[
−
10
10
,
10
10
]
[-10^{10}, 10^{10}]
[−1010,1010] 内）。 - 由于
∣
a
i
∣
≤
10
9
|a_i| \\le 10^9
∣ai∣≤109，构造出的b
i
b_i
bi 绝对值不会超过2
×
10
9
2 \\times 10^9
2×109，必然满足约束，因此答案永远不会是−
1
-1
−1（该分支仅为格式完备保留）。 - 时间复杂度
O
(
n
)
O(n)
O(n)。
解题思路
本题是构造 + 贪心的经典问题。给定一个长度为
n
n
n 的数组
a
a
a，需要构造一个数组
b
b
b，使得
a
i
+
b
i
a_i + b_i
ai+bi 构成非递减序列，并且数组
b
b
b 的极差（最大值减最小值）尽可能小。要求输出任意一个满足条件的
b
b
b 数组。
1. 问题等价转化
- 设最终序列为
f
i
=
a
i
+
b
i
f_i = a_i + b_i
fi=ai+bi。要求f
f
f 非递减，即f
1
≤
f
2
≤
⋯
≤
f
n
f_1 \\le f_2 \\le \\dots \\le f_n
f1≤f2≤⋯≤fn。 - 数组
b
b
b 的极差为max
(
b
i
)
−
min
(
b
i
)
=
max
(
f
i
−
a
i
)
−
min
(
f
i
−
a
i
)
\\max(b_i) – \\min(b_i) = \\max(f_i – a_i) – \\min(f_i – a_i)
max(bi)−min(bi)=max(fi−ai)−min(fi−ai)。 - 由于我们可以对
b
b
b 整体平移（同时加上或减去一个常数），极差不变，因此不妨令min
(
b
i
)
=
0
\\min(b_i) = 0
min(bi)=0，即存在某个i
i
i 使得b
i
=
0
b_i = 0
bi=0，从而f
i
=
a
i
f_i = a_i
fi=ai。 - 为了使
f
f
f 非递减且b
i
≥
0
b_i \\ge 0
bi≥0，一个自然的构造是令f
i
f_i
fi 等于a
a
a 的前缀最大值：f
i
=
pmx
i
=
max
j
≤
i
a
j
f_i = \\text{pmx}_i = \\max_{j \\le i} a_j
fi=pmxi=j≤imaxaj 这样f
i
f_i
fi 显然非递减，且f
i
≥
a
i
f_i \\ge a_i
fi≥ai，所以b
i
=
pmx
i
−
a
i
≥
0
b_i = \\text{pmx}_i – a_i \\ge 0
bi=pmxi−ai≥0。当a
i
a_i
ai 本身是前缀最大值时，b
i
=
0
b_i = 0
bi=0，因此min
(
b
i
)
=
0
\\min(b_i) = 0
min(bi)=0。 - 此时
b
b
b 的极差为：max
i
b
i
−
min
i
b
i
=
max
i
(
pmx
i
−
a
i
)
−
0
=
max
i
(
pmx
i
−
a
i
)
\\max_i b_i – \\min_i b_i = \\max_i (\\text{pmx}_i – a_i) – 0 = \\max_i (\\text{pmx}_i – a_i)
imaxbi−iminbi=imax(pmxi−ai)−0=imax(pmxi−ai) 可以证明，这个值就是所有合法构造中极差的最小值（与另一种后缀最小值构造得到的极差相等）。因此该构造即为最优解。
2. 算法实现
n
n
n 和数组
a
a
a。
i
=
1
∼
n
i = 1 \\sim n
i=1∼n：
- 更新 mx = max(mx, a[i])。
- 计算 b[i] = mx – a[i]。
3. 复杂度分析
- 时间复杂度：只需一次线性遍历，
O
(
n
)
O(n)
O(n)。n
≤
2
×
10
5
n \\le 2 \\times 10^5
n≤2×105，非常快。 - 空间复杂度：需要存储数组
a
a
a 和b
b
b，O
(
n
)
O(n)
O(n)。也可以边读边算，只存b
b
b。
总结
通过令最终序列等于原数组的前缀最大值，构造出的
b
i
=
pmx
i
−
a
i
b_i = \\text{pmx}_i – a_i
bi=pmxi−ai 保证了最终序列非递减，且
b
i
≥
0
b_i \\ge 0
bi≥0，最小值必为
0
0
0。此时极差等于最大的前缀差值，该值被证明是最小的。算法简单高效，直接输出即可。
代码简要说明
- 使用 long long 存储数组，防止溢出。
- INF 取 0x3f3f3f3f3f3f3f3f 作为极小值初始化 mx。
- 遍历数组，维护前缀最大值 mx，同时计算 b[i] = mx – a[i]。
- 最后按顺序输出 b 数组，空格分隔。
代码内容
#include <bits/stdc++.h>
using namespace std;
#define endl '\\n'
typedef long long ll;
typedef unsigned long long ull;
typedef vector<vector<ll>> vvt;
typedef pair<ll,ll> pll;
const ll N=1e3+10;
const ll INF=0x3f3f3f3f3f3f3f3f;
const ll M=1e6+10;
const ll mod=1000000007;
ll a[200005];
ll b[200005];
void solve()
{
ll n;
cin>>n;
for(ll i=1;i<=n;i++) cin>>a[i];
ll mx=–INF;
for(ll i=1;i<=n;i++)
{
if(a[i]>mx) mx=a[i];
b[i]=mx–a[i];
}
for(ll i=1;i<=n;i++) cout<<b[i]<<" ";
cout<<endl;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
int t=1;
while(t—) solve();
return 0;
}
评论前必须登录！
注册