1 条题解
-
0
#include <bits/stdc++.h> using namespace std; // 全局数组:arr存储有序原数组,arr1存储待查询的数值 int arr[100010], arr1[100010]; // [1] 二分查找函数:在有序数组arr[0..b-1]中,找第一个≥a的元素的1-based位置 // 找到则返回位置,否则返回-1 int f(int a, int b){ int left = 0, right = b; // 二分边界:左闭右开区间 [left, right) while(left < right){ int mid = (left + right) / 2; if(a < arr[mid]){ right = mid; // 目标值在左半区间 }else if(a > arr[mid]){ left = mid + 1; // 目标值在右半区间 }else{ right = mid; // 找到等于a的元素,继续向左找第一个≥a的位置 } } // 循环结束后left=right,检查该位置元素是否≥a if(arr[left] >= a) return left + 1; // 转换为1-based位置 else return -1; // 未找到满足条件的元素 } int main(){ int n, q; // [2] n:原数组元素个数;q:查询次数 cin >> n; // [3] 输入有序原数组 for(int i = 0; i < n; i++) cin >> arr[i]; cin >> q; // [4] 输入所有待查询的数值 for(int i = 0; i < q; i++) cin >> arr1[i]; // [5] 处理每个查询并输出结果 for(int i = 0; i < q; i++){ int res = f(arr1[i], n); cout << res << " "; } return 0; }
- 1
信息
- ID
- 1217
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 1
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者