题目思路分析

1. 问题理解

我们有 N 个朋友，每个朋友 i：

• 在时间 Ci 前有空（拜访必须在 Ci 时刻前完成）。
• 小慧计划在 S + Ti 时刻拜访他（S 是小慧的起床时间）。

我们需要回答 Q 次询问：

• 每次询问给出小慧的目标拜访人数 V 和她的起床时间 S。
• 判断在 S 时刻起床，她能否至少拜访 V 个朋友。

2. 关键条件

拜访朋友 i 成功的条件是：

S + T_i < C_i

变形为：

S < C_i - T_i

这个条件非常重要，它告诉我们：

• 每个朋友能否被成功拜访，只与小慧的起床时间 S 和一个固定值 C_i - T_i 有关。
• 我们可以预处理出所有朋友的 C_i - T_i，然后在查询时，只需要统计有多少个 C_i - T_i 大于 S。

3. 预处理与排序

为了快速统计大于某个值的元素数量，我们可以：

1. 预处理：计算每个朋友的 C_i - T_i，存储在数组 rec[] 中。
2. 排序：将 rec[] 数组升序排序。

排序后，所有大于某个值 S 的元素会集中在数组的右侧。

4. 查询处理

对于每次查询 (V, S)：

• 我们需要找到有多少个 rec[i] > S。
• 在升序数组中，大于 S 的元素的个数 = n - pos + 1，其中 pos 是第一个大于 S 的元素的下标。
• 可以用 二分查找 在 O(log n) 时间内找到这个 pos。

5. 时间复杂度分析

• 预处理：
  • 计算 rec[]：O(N)
  • 排序 rec[]：O(N log N)
• 查询：
  • 每次查询二分查找：O(log N)
  • 总查询时间：O(Q log N)

总体复杂度：O(N log N + Q log N)，适用于数据范围 N, Q <= 1e5。

代码详细注释

#include <bits/stdc++.h>
#define int long long // 定义 int 为 long long，防止溢出
const int N = 1e5 + 10; // 最大数据量
using namespace std;

int n, q; // n: 朋友数量, q: 查询次数
int c[N], t[N], rec[N]; // c[i]: 朋友i的空闲截止时间, t[i]: 拜访i所需时间, rec[i]: c[i]-t[i]
int v, s; // v: 目标拜访人数, s: 起床时间

// 二分查找函数: 返回大于 s 的 rec[i] 的数量
int bs(int x) { 
    int l = 1, r = n, ans = 0; // l: 左边界, r: 右边界, ans: 记录第一个大于 x 的位置
    while (l <= r) { // 二分查找循环
        int mid = (l + r) >> 1; // 计算中间位置
        if (rec[mid] > x) { // 如果中间值大于 x
            ans = mid; // 记录当前位置为候选答案
            r = mid - 1; // 向左搜索，寻找更左边的大于 x 的值
        } else { // 否则
            l = mid + 1; // 向右搜索
        }
    }
    if (ans == 0) return 0; // 如果没有找到大于 x 的值，返回 0
    else return n - (ans - 1); // 否则返回大于 x 的元素数量
}

signed main() {
    scanf("%lld%lld", &n, &q); // 读取朋友数量和查询次数
    for (int i = 1; i <= n; i++) scanf("%lld", c + i); // 读取每个朋友的空闲截止时间
    for (int i = 1; i <= n; i++) scanf("%lld", t + i); // 读取拜访每个朋友所需时间
    for (int i = 1; i <= n; i++) rec[i] = c[i] - t[i]; // 计算 rec[i] = c[i] - t[i]
    sort(rec + 1, rec + 1 + n); // 对 rec 数组升序排序
    for (int i = 1; i <= q; i++) { // 处理每个查询
        scanf("%lld%lld", &v, &s); // 读取目标人数 v 和起床时间 s
        int tem = bs(s); // 计算能拜访的朋友数量
        if (tem >= v) printf("YES\n"); // 如果数量 >= v，输出 YES
        else printf("NO\n"); // 否则输出 NO
    }
    return 0;
}

总结

• 核心思路：将拜访成功的条件转化为对 C_i - T_i 的统计问题。
• 优化手段：通过排序和二分查找，将每次查询的时间复杂度从 O(N) 降为 O(log N)。
• 代码特点：预处理简单，查询高效，适用于大规模数据。