小欧的数组构造

OPPO 笔试真题 · 2024 秋招 · 移动端

判题请到牛客原题提交。

题目描述

小欧有一个整数数组 $a$ ，她已经忘记了 $a$ 数组的构成，但她还记得 $b$ 数组， $b$ 数组中的每一项记录的是 $a$ 数组两个相邻的数之和，也就是说 $b_i = a_i+a_{i+1}(1 \leq i \leq n-1)$ 。

小欧很喜欢正数，她想知道在原来的 $a$ 数组中最多可能有几个正数，请输出最多可能的正数个数

输入格式

第一行输入一个整数 $n(2 \leq n \leq 10^5)$ 表示数组长度。

第二行输入 $n-1$ 个整数表示数组 $b(-10^9 \leq b_i \leq 10^9)$ 。

输出格式

输出一个整数表示答案。

示例

示例 1

输入：

3
1 2

输出：

2

说明：

a数组可能是[1,0,2],[2,-1,3],[0,1,1],[-2,3,-1]等，但可以证明，正数数量最多只可能是2。

---

解题思路

第一步：理解问题本质

我们只知道 $n-1$ 个数 $b_i=a_i+a_{i+1}$，不知道 $a$ 本身。
方程有 $n-1$ 个、未知数有 $n$ 个，所以自由度是 1：
只要确定 $a_1$，其余的数就被唯一确定了。

$$a_2=b_1-a_1,\quad a_3=b_2-a_2,\quad a_4=b_3-a_3,\ \dots$$

我们要挑一个 $a_1$，让 $a$ 里正数的个数尽可能多。

第二步：暴力解法

枚举 $a_1$ 的取值，每种取值都递推一遍求出 $a$，数一数有几个正数。

问题在于 $a_1$ 可以取任意整数（范围无界），枚举不现实；
即使只看「有意义的范围」，$n=10^5$ 时整个做法也至少是
$O(n \times V)$ 的量级（$V$ 是枚举范围的大小）。这个方法只能用来验证小数据。

第三步：写出通项

把递推展开，观察 $a_i$ 与 $a_1=x$ 的关系：

$$\begin{aligned} a_1 &= x\\ a_2 &= b_1-x\\ a_3 &= b_2-a_2=b_2-b_1+x\\ a_4 &= b_3-a_3=b_3-b_2+b_1-x \end{aligned}$$

$x$ 的符号在交替变化，常数项则一级一级往下减。把它写成统一形式：

$$a_i=c_i+s_i\cdot x,\qquad s_i=(-1)^{i-1},\quad c_1=0,\quad c_{i+1}=b_i-c_i$$

也就是说：奇数位是 $c_i+x$，偶数位是 $c_i-x$。

第四步：把「正数」变成对 $x$ 的单侧限制

要求 $a_i>0$（正数，不含 0）：

• 若 $i$ 是奇数：$c_i+x>0\Rightarrow x\ge -c_i+1$，这是对 $x$ 的下界；
• 若 $i$ 是偶数：$c_i-x>0\Rightarrow x\le c_i-1$，这是对 $x$ 的上界。

于是问题变成：选一个整数 $x$，让它满足尽量多的这种「单侧限制」。
每个限制只关心 $x$ 在某个分界点的哪一侧。

第五步：扫描分界点

「满足的个数」只会在分界点处变化，所以不用枚举 $x$，只要看这些点：

• 奇数位的限制在 $x=-c_i+1$ 处开始生效，记为 $+1$；
• 偶数位的限制在 $x=c_i$ 处失效（因为条件只到 $c_i-1$ 为止），记为 $-1$；
• 当 $x\to-\infty$ 时，所有偶数位都满足、所有奇数位都不满足，
  所以起点是「偶数位的个数」。

把所有事件按 $x$ 从小到大排序，维护一个计数器，途中出现的最大值就是答案。

---

完整代码实现

import sys


def solve():
    """把每个 a_i > 0 化成对 a_1 = x 的区间限制，扫描分界点求最大值"""
    data = sys.stdin.buffer.read().split()
    if not data:
        return
    n = int(data[0])
    b = [int(t) for t in data[1:1 + n - 1]]

    # c_1 = 0，c_i = b_{i-1} - c_{i-1}
    delta = {}          # x 走到这个位置时，「满足条件的个数」的变化量
    cur = 0             # 当前有 cur 个限制成立
    c = 0
    for i in range(1, n + 1):
        if i == 1:
            c = 0
        else:
            c = b[i - 2] - c
        if i % 2 == 1:
            # a_i = c + x > 0  =>  x >= -c + 1，即 x 到达该点时这个限制才成立
            pos = -c + 1
            delta[pos] = delta.get(pos, 0) + 1
        else:
            # a_i = c - x > 0  =>  x <= c - 1，即 x 越过 c-1 之后这个限制失效
            cur += 1                     # x 取 -inf 时偶数位全部为正
            pos = c                      # 走到 x = c 时 -1
            delta[pos] = delta.get(pos, 0) - 1

    best = cur
    for pos in sorted(delta):
        cur += delta[pos]
        if cur > best:
            best = cur

    sys.stdout.write(str(best) + "\n")


if __name__ == "__main__":
    solve()

---

示例推演

样例：$n=3$，$b=[1,2]$。

第一步：算出常数项

• $c_1=0$
• $c_2=b_1-c_1=1-0=1$
• $c_3=b_2-c_2=2-1=1$

于是

$$a_1=x,\qquad a_2=1-x,\qquad a_3=1+x$$

第二步：化成对 $x$ 的限制

位置	表达式	要求	对 $x$ 的限制	事件
1（奇）	$x$	$x>0$	$x\ge 1$	在 $x=1$ 处 $+1$
2（偶）	$1-x$	$1-x>0$	$x\le 0$	在 $x=1$ 处 $-1$
3（奇）	$1+x$	$1+x>0$	$x\ge 0$	在 $x=0$ 处 $+1$

第三步：扫描

• 起点 $x\to-\infty$：只有 2 号位满足，计数 $=1$，最大值 $=1$；
• 走到 $x=0$：3 号位开始满足，计数 $=2$，最大值 $=2$；
• 走到 $x=1$：1 号位开始满足（$+1$），同时 2 号位失效（$-1$），计数仍是 2。

所以答案是 2。

第四步：验证

取 $x=0$，得到 $a=[0,1,1]$：$a_1+a_2=1=b_1$、$a_2+a_3=2=b_2$，
确实是一个合法解，其中正数有 2 个（0 不算正数）。
这和题面说明里的 [0,1,1] 一致。

再取 $x=1$，得到 $a=[1,0,2]$，同样有 2 个正数 —— 最优值 2 有多组解。

---

复杂度分析

解法	时间复杂度	空间复杂度	说明
枚举 $a_1$ 并逐个递推	$O(n\cdot V)$	$O(n)$	$V$ 是枚举范围，而 $a_1$ 本身无界，无法使用
通项 + 事件扫描	$O(n\log n)$	$O(n)$	推荐，代价只有一次排序

---

易错点总结

1. 通项的符号写反

奇数位是 $c_i+x$、偶数位是 $c_i-x$。如果写反，所有上下界都会错位一项，
样例可能仍然「碰巧」正确，但换成别的数据就崩了。

2. 偶数位的分界点是 $c_i$，不是 $c_i-1$

条件是不等式 $c_i-x>0$，即 $x\le c_i-1$，所以它在 $x=c_i$ 时失效。
事件位置写错 1，答案就会差 1。

3. 0 不是正数

题目问的是正数，严格大于 0，所以奇数位的下界要 $+1$（$x\ge -c_i+1$）。
写成 $x\ge -c_i$ 会把 $a_i=0$ 也算进去。

4. 扫描的起点是「偶数位的个数」

$x\to-\infty$ 时偶数位 $c_i-x$ 必然为正，奇数位 $c_i+x$ 必然为负或零。
起点写 0 会漏掉「$x$ 取很小的负数」这一整类方案。

5. 数值范围

$b_i$ 可以到 $10^9$、$n$ 到 $10^5$，$c_i$ 交替累加后可能达到 $10^{14}$ 量级。
Python 整数不会溢出；用 C++ 写时 $c_i$、$x$ 都要用 long long。

6. 不要假设 $x\ge 0$

$x$ 是原数组的第一个元素，可以是负数。题面说明里的 [-2,3,-1]
就来自 $x=-2$，只枚举非负的 $x$ 会漏掉不少情况。

---

扩展思考

• 若改成统计「最多的非负数」，只需把 $a_i>0$ 换成 $a_i\ge 0$，
  所有分界点整体左移 1，骨架完全不变。
• 若约束变成 $b_i=p\cdot a_i+q\cdot a_{i+1}$，通项里 $x$ 的系数会变成
  $(-q/p)^{i-1}$，不再交替取 $\pm1$，比较大小就变成有理数（或浮点 + 精度）问题。
• 若再要求 $a$ 单调递增，那么「对 $x$ 的单侧限制」会变成「$x$ 的区间」，
  求交集即可，反而更简单。
• 这类题的通用套路：一个自由变量 + 每个位置给出一个关于它的不等式，
  答案就是被最多区间覆盖的那个点，用「差分 + 扫描线」处理。

---

相关题目

• 小欧的数组修改
• 小欧的等差数列