问题描述 有一条公路，由N段组成，各段限速不一定相同。有一辆汽车通过此条公路，通过GPS定位获得该车的速度和该速度下行驶的路程。求该辆汽车通过此条公路的最大超速。 输入描述 第一行2个正整数N,M 以下N行，每行两个两个整数，表示区间里程和限速，所有区间里程之和不超过1000公里。 接下来M行，每行两个整数，表示通过里程和实际行驶速度，总里程为该公里总里程。 输出描述 一个整数，表示最大超速值 输入样例 3 3 40 75 50 35 10 45 40 76 20 30 40 40 输出样例 5 数据范围 N<=100 M<=100用c++代码实现

以下是用 C++ 实现的代码：

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

const int N = 110, INF = 0x3f3f3f3f;
int n, m;
int d[N], s[N];
int l[M], v[M];

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> d[i] >> s[i];
    }
    for (int i = 1; i <= m; i++) {
        cin >> l[i] >> v[i];
    }
    int ans = -INF;
    for (int i = 1; i <= m; i++) {
        int j = 1, k = 1, dist = 0, speed = 0;
        while (j <= n && k <= m) {
            if (dist + d[j] <= l[i]) {
                dist += d[j];
                speed = min(speed, s[j]);
                j++;
            } else {
                int t = l[i] - dist;
                speed = min(speed, s[j]);
                ans = max(ans, v[i] - speed);
                k++;
                if (k <= m) {
                    dist = 0;
                    for (int p = j; p <= n; p++) {
                        if (dist + d[p] > t) {
                            d[p] -= t - dist;
                            break;
                        } else {
                            dist += d[p];
                            s[p] = INF;
                        }
                    }
                }
            }
        }
    }
    cout << ans << endl;
    return 0;
}

思路如下：

首先读入公路的信息和汽车通过信息。

对于每一次汽车通过，我们可以将路程分为两部分：已经通过的部分和还未通过的部分。我们用双指针 $j$ 和 $k$ 分别指向已经通过的最远位置和还未通过的最近位置。然后分两种情况讨论：

1. 如果加上下一段路程后不超过目标位置，那么就将下一段路程加入已经通过的部分，速度取当前最小速度。

2. 如果加上下一段路程后超过目标位置，那么就需要将这一段路程拆分成两部分，一部分加入已经通过的部分，一部分留待下一次通过。具体做法是从已经通过的部分的最后一段开始，依次减去每一段路程，直到刚好到达目标位置。在此过程中，如果某一段路程被完全减去，则将其速度赋为无穷大，表示汽车不可能再经过这段路程了。然后更新 $k$，即表示已经通过的部分的位置发生了改变。

在每次更新 $k$ 时，计算当前汽车通过的最大超速，并更新答案。

最终输出答案即可。

时间复杂度为 $O(nm^2)$，可以通过此题。