小欧的数组构造

[题目链接](https://www.nowcoder.com/practice/7e86d90777ad41e4a59d2e937bf9afc2)

思路

已知长度为 $n-1$ 的数组 $b$ ，其中 $b_i = a_i + a_{i+1}$ ，要求构造长度为 $n$ 的整数数组 $a$ ，使 $a$ 中正数个数最多。

$a_0$ 决定一切

一旦确定了 $a_0$ 的值，整个数组就被唯一确定了： $a_1 = b_0 - a_0$ ， $a_2 = b_1 - a_1$ ，依此类推。展开后可以发现：

$ $a_i = (-1)^i \cdot a_0 + c_i$ $

其中 $c_0 = 0$ ， $c_{i+1} = b_i - c_i$ 。也就是说， $a_i$ 关于 $a_0$ 是线性的，且系数在 $+1$ 和 $-1$ 之间交替。

转化为不等式计数

要让 $a_i > 0$ （正数），分两种情况：

偶数下标 $i$ ： $a_0 + c_i > 0$ ，即 $a_0 \geq -c_i + 1$ （因为 $a_0$ 是整数）
奇数下标 $i$ ： $-a_0 + c_i > 0$ ，即 $a_0 \leq c_i - 1$

注意偶数下标希望 $a_0$ 尽量大，奇数下标希望 $a_0$ 尽量小，两者互相矛盾。我们要找一个整数 $a_0$ ，使满足的不等式总数最多。

扫描线求解

把每个约束看成数轴上的一个事件：

偶数下标 $i$ ：在 $x = -c_i + 1$ 处放一个 $+1$ 事件——当 $a_0$ 达到这个值时，多满足一个约束
奇数下标 $i$ ：在 $x = c_i$ 处放一个 $-1$ 事件——当 $a_0$ 达到这个值时，少满足一个约束

初始时（ $a_0 \to -\infty$ ），所有偶数约束都不满足，所有奇数约束都满足，所以初始得分 = 奇数下标的个数。

将所有事件按坐标排序，从左到右扫描并累加 delta，过程中维护得分的最大值即为答案。

样例验证

$n = 3$ ， $b = [1, 2]$ ， $c = [0, 1, 1]$ 。

事件列表：

$i=0$ （偶）： $(1, +1)$
$i=1$ （奇）： $(1, -1)$
$i=2$ （偶）： $(0, +1)$

排序后： $(0, +1)$ 、 $(1, +1)$ 、 $(1, -1)$ 。初始得分 = 1。

$x = 0$ ：得分 = $1 + 1 = 2$
$x = 1$ ：得分 = $2 + 1 - 1 = 2$

最大得分 = 2，与答案一致。对应 $a_0 = 0$ 时 $a = [0, 1, 1]$ （2 个正数）。

代码

C++
Java

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    scanf("%d", &n);
    vector<long long> b(n - 1);
    for (int i = 0; i < n - 1; i++) scanf("%lld", &b[i]);

    vector<long long> c(n);
    c[0] = 0;
    for (int i = 0; i < n - 1; i++) c[i + 1] = b[i] - c[i];

    int countOdd = 0;
    vector<pair<long long, int>> events;
    for (int i = 0; i < n; i++) {
        if (i % 2 == 0) {
            events.push_back({-c[i] + 1, +1});
        } else {
            events.push_back({c[i], -1});
            countOdd++;
        }
    }
    sort(events.begin(), events.end());

    int score = countOdd, best = score;
    int idx = 0;
    while (idx < (int)events.size()) {
        long long val = events[idx].first;
        int delta = 0;
        while (idx < (int)events.size() && events[idx].first == val) {
            delta += events[idx].second;
            idx++;
        }
        score += delta;
        best = max(best, score);
    }
    printf("%d\n", best);
    return 0;
}

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine().trim());
        StringTokenizer st = new StringTokenizer(br.readLine().trim());
        long[] b = new long[n - 1];
        for (int i = 0; i < n - 1; i++) b[i] = Long.parseLong(st.nextToken());

        long[] c = new long[n];
        c[0] = 0;
        for (int i = 0; i < n - 1; i++) c[i + 1] = b[i] - c[i];

        int countOdd = 0;
        long[][] events = new long[n][2];
        for (int i = 0; i < n; i++) {
            if (i % 2 == 0) {
                events[i][0] = -c[i] + 1;
                events[i][1] = 1;
            } else {
                events[i][0] = c[i];
                events[i][1] = -1;
                countOdd++;
            }
        }
        Arrays.sort(events, (a, bb) -> Long.compare(a[0], bb[0]));

        int score = countOdd, best = score;
        int idx = 0;
        while (idx < n) {
            long val = events[idx][0];
            int delta = 0;
            while (idx < n && events[idx][0] == val) {
                delta += (int) events[idx][1];
                idx++;
            }
            score += delta;
            best = Math.max(best, score);
        }
        System.out.println(best);
    }
}

复杂度分析

时间复杂度： $O(n \log n)$ ，瓶颈在于对事件排序。
空间复杂度： $O(n)$ ，存储 $c$ 数组和事件数组。