概述

本题要求根据相邻整数点函数值的符号变化，利用零点存在定理确定区间 ~(0,N)~ 内至少有多少个零点。核心解法是统计相邻点函数值乘积为负的次数，每出现一次即至少存在一个零点。

分析

核心观察

零点存在定理指出，若连续函数在两个端点处的函数值异号，则区间内至少有一个零点。因此，只需检查所有相邻整数点 ~(i, i+1)~，若 ~\phi(i) \cdot \phi(i+1) < 0~，则区间 ~(i, i+1)~ 内必有一个零点。不同区间相互独立，总零点数至少为这些区间的数量。

思路

设给定序列为 ~a_0, a_1, \dots, a_N~，其中 ~a_i = \phi(i)~ 且均非零。对于每个 ~i = 0, 1, \dots, N-1~，若 ~a_i~ 与 ~a_{i+1}~ 异号（即乘积为负），则根据零点存在定理，区间 ~(i, i+1)~ 内至少有一个零点。由于这些区间互不重叠，零点数量可累加。答案为满足 ~a_i \cdot a_{i+1} < 0~ 的 ~i~ 的个数。由于数据保证 ~a_i \neq 0~，乘积符号可直接通过比较正负判断。

具体示例

样例序列 ~[-2, 1, 3, -2, 1, 2]~，相邻异号对为：

• ~(-2, 1)~ 异号 → 零点在 ~(0,1)~
• ~(1, 3)~ 同号
• ~(3, -2)~ 异号 → 零点在 ~(2,3)~
• ~(-2, 1)~ 异号 → 零点在 ~(3,4)~
• ~(1, 2)~ 同号 总计 ~3~ 个。

算法步骤

1. 读取整数 N。
2. 读取长度为 ~N+1~ 的数组 a，存储 ~\phi(0)~ 到 ~\phi(N)~。
3. 初始化计数器 cnt 为 ~0~。
4. 遍历 i 从 ~0~ 到 ~N-1~：
   • 若 a[i] * a[i+1] < 0，将 cnt 加 ~1~。
5. 输出 cnt。

复杂度分析

• 时间：~O(N)~
• 空间：~O(N)~

实现注意事项

• 函数值绝对值可达 ~10^9~，乘积可能达到 ~10^{18}~，需使用 64 位整数（long long）存储以避免溢出。
• 输入数据保证所有值非零，因此无需处理零值情况，但比较符号时直接判断 (a[i] > 0) != (a[i+1] > 0) 可避免乘法溢出，更安全。
• N 最大为 ~10^5~，数组大小适中。

源代码

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int N;
    cin >> N;
    vector<long long> a(N + 1);
    for (int i = 0; i <= N; ++i) {
        cin >> a[i];
    }

    int ans = 0;
    for (int i = 0; i < N; ++i) {
        if ((a[i] > 0) != (a[i + 1] > 0)) {
            ++ans;
        }
    }

    cout << ans << endl;
    return 0;
}

N = int(input())
a = list(map(int, input().split()))

ans = 0
for i in range(N):
    if (a[i] > 0) != (a[i + 1] > 0):
        ans += 1

print(ans)