1 条题解

  • 0
    @ 2026-2-2 16:56:23
    #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
    上传者