1 条题解
-
0
#include<bits/stdc++.h> using namespace std; // [1] 全局变量:n为元素总数,q为查询次数 int n,q; // [2] 结构体:存储元素数值及原始位置,为排序和查询做数据支撑 struct stu{ int num; // 存储元素的数值 int v; // 存储元素在原数组中的位置(从1开始计数) }; // [3] 全局向量容器:存放所有元素的数值和原始位置信息 vector<stu> arr; // 排序比较函数(主函数调用时跳转注释) // [8] 排序规则:按元素的数值num进行升序排列,为二分查找做有序准备 bool cmp(stu x,stu y){ return x.num < y.num; } // 二分查找函数(主函数调用时跳转注释) // [9] 二分查找核心函数:在有序arr中查找目标值x,找到返回其索引,未找到返回-1 int find(int x){ // [10] 初始化二分查找左右边界,覆盖整个有序数组 int l=0, r=n-1; // [11] 二分查找主循环:不断缩小查找区间,直至找到目标或区间失效 while(l <= r){ int mid = l + (r-l)/2; // 计算中间位置,避免l+r直接相加导致数值溢出 if(arr[mid].num > x){ r = mid - 1; // 目标在左半区间,调整右边界 }else if(arr[mid].num < x){ l = mid + 1; // 目标在右半区间,调整左边界 }else{ return mid; // 找到目标值,返回其在有序数组中的索引 } } return -1; // 区间遍历完毕,未找到目标值 } int main() { // [4] 输入元素总个数,确定数据规模 cin >> n; // [5] 初始化向量容量,匹配元素个数,避免动态扩容 arr.resize(n); // [6] 循环输入所有元素,同时记录每个元素的原始位置 for(int i=0; i<n; i++){ cin >> arr[i].num; // 输入当前元素的数值 arr[i].v = i + 1; // 记录元素原始位置,从1开始计数 } // [7] 对元素进行升序排序,为后续二分查找提供有序数组 sort(arr.begin(), arr.end(), cmp); // [12] 输入查询次数,确定需要处理的查询任务量 cin >> q; // [13] 循环处理所有查询请求,逐个返回查询结果 for(int i=1; i<=q; i++){ int a; cin >> a; // 输入当前需要查询的目标数值 int w = find(a); // 调用二分查找,获取目标值索引(未找到为-1) // [14] 根据查找结果,输出对应答案 if(w == -1){ cout << 0 << endl; // 未找到目标值,输出0 }else{ cout << arr[w].v << endl; // 找到目标值,输出其原始位置 } } return 0; }
- 1
信息
- ID
- 1222
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 2
- 标签
- 递交数
- 2
- 已通过
- 1
- 上传者