【CSP试题回顾】202112-2-序列查询新解

本文主要是介绍【CSP试题回顾】202112-2-序列查询新解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

CSP-202112-2-序列查询新解

关键点：时间复杂度

本题关键在于它避免暴力枚举法的时间复杂度。暴力枚举法可能会对每一对可能的 f(x) 和 g(x) 组合进行比较，其时间复杂度为 $O(n^2)$ ，这对于大数据集来说是不可行的。

【解决思路】：通过逐步遍历 f(x) 和 g(x) 的值（每次只移动到下一个 f(x) 或 g(x) 值），将时间复杂度降低到了 $O (n)$ 。这种方法只需要遍历一次 f(x) 和 g(x) 的所有值，大大减少了计算量。
这种方法的效率提高主要是因为它保持了 f(x) 和 g(x) 索引的逻辑顺序，这样就能在单个循环内完成所有的计算，避免了不必要的重复比较。

解题思路

1.初始化

Fi 和 Gi 分别是 f(x) 和 g(x) 当前索引的指针，初始值都设置为 0。
lastIndex 表示最近处理的点的位置，初始化为 0。
error 用于累积总误差，也是从 0 开始的。

2.遍历过程

循环条件：while 循环会持续，直到 Fi 或 Gi 其中一个超过各自数组的长度。确保所有的 f(x) 和 g(x) 值都被遍历。
找到下一个处理点（重要）：循环中，首先确定下一个处理点的位置 nextIndex。这是当前 f(x)（由 arrF_x[Fi] 给出）和 g(x)（由 arrG_x[Gi] 给出）值中较小的一个。这个点是当前关注的位置，因为它表示下一个即将处理的 f(x) 或 g(x) 的值。
计算长度和误差（重要）：根据 nextIndex 和 lastIndex（上一个点的位置），计算这两点之间的距离 length = nextIndex - lastIndex。然后，利用这段长度和 Fi 与 Gi 之间的差的绝对值更新总误差 error。这个差的绝对值代表在此段中 f(x) 和 g(x) 之间的偏差。
更新索引（重要）：如果 arrF_x[Fi]（当前 f(x) 的值）是 nextIndex，那么 Fi 自增以移动到 f(x) 的下一个值。同样，如果 arrG_x[Gi]（当前 g(x) 的值）是 nextIndex，那么 Gi 自增以移动到 g(x) 的下一个值。这个步骤确保了在每次迭代后，Fi 和 Gi 至少有一个向前移动。
重复过程：更新 lastIndex 为 nextIndex，然后重复循环，直到遍历完所有的 f(x) 和 g(x) 值。

3.逐步遍历的意义

通过逐步遍历，代码能够有效地计算在每一小段上 f(x) 和 g(x) 的近似误差，并累积这些误差以得到整体误差。这种方法利用了线性遍历的策略，减少了计算复杂度，相比暴力方法有显著的性能提升。

完整代码

#include<iostream>
#include<vector>
using namespace std;long long n, N, error, r;int main() {   cin >> n >> N; // 输入n和Nr = N / (n + 1); // 计算每个区间的长度vector<long long> arrF_x(n); // 存储f(x)的值for (int i = 0; i < n; i++) {cin >> arrF_x[i]; // 输入f(x)的值}arrF_x.push_back(N); // 将N作为最后一个f(x)的值，确保能够覆盖全部范围vector<long long> arrG_x; // 存储g(x)的值for (int i = r; i < N; i += r) {arrG_x.push_back(i); // 按照间隔r生成g(x)的值}if (arrG_x.back() != N) { // 确保N也作为g(x)的一个值arrG_x.push_back(N);}long long Fi = 0, Gi = 0, lastIndex = 0; // 初始化索引和上一个点的位置while (Fi < arrF_x.size() && Gi < arrG_x.size()) { // 遍历f(x)和g(x)long long nextIndex = min(arrF_x[Fi], arrG_x[Gi]); // 找到下一个处理点的位置long long length = nextIndex - lastIndex; // 计算两点之间的长度lastIndex = nextIndex; // 更新上一个点的位置error += length * abs(Fi - Gi); // 更新误差if (arrF_x[Fi] == nextIndex) Fi++; // 如果f(x)到达下一个点，则移动Fiif (arrG_x[Gi] == nextIndex) Gi++; // 如果g(x)到达下一个点，则移动Gi}cout << error; // 输出总误差return 0;
}