P4783 灾区救援（基础）

解题思路

第一步，读懂题目。 n 辆卡车按载重量从小到大排好队，载重量可能相同。有 q 次询问，每次问载重量 x 的卡车第一次出现在第几个位置、最后一次出现在第几个位置（位置从 1 开始）。如果没有这种卡车，输出 -1 -1。

第二步，发现数组已经有序。 卡车是按载重量从小到大排好的，所以可以直接在有序数组上用二分查找，非常快。

第三步，找第一次出现的位置。 第一次出现的位置，就是数组中第一个大于等于 x 的位置。我们用二分查找 lowerBound 来做：每次看中间的数，如果它大于等于 x，说明要找的位置在左半边（把右边界 right 移到 mid）；否则在右半边（把左边界 left 移到 mid+1）。循环结束后 left 就是第一个大于等于 x 的下标。

第四步，判断 x 到底存不存在。 找到 first 后还要检查一下 trucks[first] 是不是真的等于 x。如果 first 超出了数组范围，或者 trucks[first] 不等于 x，说明数组里根本没有载重量为 x 的卡车，输出 -1 -1。

第五步，找最后一次出现的位置。 最后一次出现的位置，就是第一个大于 x 的位置再往前一位。我们再用 lowerBound 找第一个大于等于 x+1 的位置，然后减 1 就是最后一个 x 的下标。因为数组有序，所有相同的 x 都排在一起。

第六步，注意位置从 1 开始。 二分找到的是下标（从 0 开始），输出时要加 1。如果 x 只出现一次，第一次和最后一次是同一个位置，比如样例里的 688 输出 “8 8”。

参考代码

// 灾区救援：载重量数组已经从小到大排好序，用两次二分查找分别找 x 第一次和最后一次出现的位置
#include <iostream>
using namespace std;

int trucks[100005];

// 二分查找数组中第一个大于等于 x 的位置，返回下标（从 0 开始）
int lowerBound(int left, int right, int x) {
    while (left < right) {
        int mid = (left + right) / 2;
        if (trucks[mid] >= x) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

int main() {
    int n, q;
    scanf("%d%d", &n, &q);
    for (int i = 0; i < n; i++) {
        scanf("%d", &trucks[i]);
    }
    for (int query = 0; query < q; query++) {
        int x;
        scanf("%d", &x);
        // 先找 x 第一次出现的位置
        int first = lowerBound(0, n, x);
        if (first == n || trucks[first] != x) {
            // 数组里没有 x
            printf("-1 -1\n");
        } else {
            // 找 x 最后一次出现的位置：第一个大于 x 的位置再减 1
            int last = lowerBound(0, n, x + 1) - 1;
            printf("%d %d\n", first + 1, last + 1);
        }
    }
    return 0;
}

复杂度分析

每次询问做两次二分查找，每次 O(log n)；q 次询问一共 O(q log n)。排序不需要（输入已有序），所以总时间就是 O(q log n)。空间 O(n)，存 n 辆卡车的载重量。