1 条题解
-
0
#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; }
- 1
信息
- ID
- 5638
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 10
- 标签
- (无)
- 递交数
- 1
- 已通过
- 0
- 上传者