小苯的数组构造【牛客tracker & 每日一题】

小苯的数组构造

时间限制：1 秒
空间限制：256M

网页链接

牛客tracker

牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！

---

题目描述

大白熊给了小苯一个长度为 $n$ 的数组 $a$，他希望小苯将数组 $a$ 变成有序（非递减）的。具体的，小苯需要进行如下操作：

1. 任选一个数组 $b$，长度也为 $n$，且元素满足：$-10^{10}\le b_i\le 10^{10}$。
2. 对于所有 $1\le i\le n$，都执行 $a_i=a_i+b_i$。

大白熊希望在执行完操作后 $a$ 数组满足有序，同时要最小化数组 $b$ 的极差，即使得：

$$\max (b_1,b_2,\dots ,b_n)-\min (b_1,b_2,\dots ,b_n)$$

最小。

请你帮小苯找出一个合法的 $b$ 数组吧。

注：如有多解输出任意即可。

---

输入描述

输入包含两行。

• 第一行一个正整数 $n(1\le n\le 2\times 10^5)$，表示 $a$ 的长度。
• 第二行 $n$ 个整数 $a_i(-10^9\le a_i\le 10^9)$，表示数组 $a$ 的元素。

---

输出描述

输出包含一行 $n$ 个整数，表示构造出的 $b$ 数组（有多解输出任意即可）。

如果找不到合法的 $b$ 数组，请输出一个整数 $-1$。

---

示例 1

输入：

2
1 2

输出：

114514 114514

说明： 可以构造 $b=[114514,114514]$，这样 $b$ 的极差为 $0$，可以证明不存在比 $0$ 更小的极差。

---

备注

数组的极差 = 数组中的最大值减去最小值。

---

数据范围与提示

• $1\le n\le 2\times 10^5$
• $-10^9\le a_i\le 10^9$
• $-10^{10}\le b_i\le 10^{10}$
• 核心思路：
  1. 记最终序列 $f_i=a_i+b_i$，要求 $f$ 非递减。$b$ 的极差等价于 ${\max }_i(f_i-a_i)-{\min }_i(f_i-a_i)$，要让它最小。
  2. 两种自然的构造可分别给出上界：
     • 取 $b_i={\mathrm{pmx}}_i-a_i$（${\mathrm{pmx}}_i$ 为前缀最大值），此时 $f_i={\mathrm{pmx}}_i$ 非递减，$b$ 的极差为 ${\max }_i({\mathrm{pmx}}_i-a_i)$；
     • 取 $b_i={\mathrm{smn}}_i-a_i$（${\mathrm{smn}}_i$ 为后缀最小值），此时 $f_i={\mathrm{smn}}_i$ 非递减，$b$ 的极差为 ${\max }_i(a_i-{\mathrm{smn}}_i)$。
  3. 最优极差为
     $$D=\min \left\{\underset{i}{\max }({\mathrm{pmx}}_i-a_i),\underset{i}{\max }(a_i-{\mathrm{smn}}_i)\right\}$$
     选择上述两种构造中更优的一种输出即可（也可以在此基础上统一平移，使得所有 $b_i$ 都落在 $[-10^{10},10^{10}]$ 内）。
• 由于 $|a_i|\le 10^9$，构造出的 $b_i$ 绝对值不会超过 $2\times 10^9$，必然满足约束，因此答案永远不会是 $-1$（该分支仅为格式完备保留）。
• 时间复杂度 $O(n)$。

解题思路

本题是构造 + 贪心的经典问题。给定一个长度为 $n$ 的数组 $a$，需要构造一个数组 $b$，使得 $a_i+b_i$ 构成非递减序列，并且数组 $b$ 的极差（最大值减最小值）尽可能小。要求输出任意一个满足条件的 $b$ 数组。

1. 问题等价转化

• 设最终序列为 $f_i=a_i+b_i$。要求 $f$ 非递减，即 $f_1\le f_2\le \cdots \le f_n$。
• 数组 $b$ 的极差为 $\max (b_i)-\min (b_i)=\max (f_i-a_i)-\min (f_i-a_i)$。
• 由于我们可以对 $b$ 整体平移（同时加上或减去一个常数），极差不变，因此不妨令 $\min (b_i)=0$，即存在某个 $i$ 使得 $b_i=0$，从而 $f_i=a_i$。
• 为了使 $f$ 非递减且 $b_i\ge 0$，一个自然的构造是令 $f_i$ 等于 $a$ 的前缀最大值：
  $$f_i={\text{pmx}}_i=\underset{j\le i}{\max }{a}_j$$
  这样 $f_i$ 显然非递减，且 $f_i\ge a_i$，所以 $b_i={\text{pmx}}_i-a_i\ge 0$。当 $a_i$ 本身是前缀最大值时，$b_i=0$，因此 $\min (b_i)=0$。
• 此时 $b$ 的极差为：
  $$\underset{i}{\max }{b}_i-\underset{i}{\min }{b}_i=\underset{i}{\max }({\text{pmx}}_i-a_i)-0=\underset{i}{\max }({\text{pmx}}_i-a_i)$$
  可以证明，这个值就是所有合法构造中极差的最小值（与另一种后缀最小值构造得到的极差相等）。因此该构造即为最优解。

2. 算法实现

1. 读入 $n$ 和数组 $a$。
2. 初始化 mx 为一个极小值（如 -INF），用于记录当前前缀最大值。
3. 遍历 $i=1\sim n$：
   • 更新 mx = max(mx, a[i])。
   • 计算 b[i] = mx - a[i]。
4. 输出数组 b。

3. 复杂度分析

• 时间复杂度：只需一次线性遍历，$O(n)$。$n\le 2\times 10^5$，非常快。
• 空间复杂度：需要存储数组 $a$ 和 $b$，$O(n)$。也可以边读边算，只存 $b$。

总结

通过令最终序列等于原数组的前缀最大值，构造出的 $b_i={\text{pmx}}_i-a_i$ 保证了最终序列非递减，且 $b_i\ge 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;
}

转载自 CSDN-专业IT技术社区

原文链接：https://blog.csdn.net/2301_80065123/article/details/167033379