1 条题解

  • 0
    @ 2026-1-28 15:36:02
    #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{
                left = mid + 1; // 找到等于a的元素,继续向右找最后一次出现的位置
            }
        }
        // 循环结束后left=right,检查最后一个可能的位置
        if(right > 0 && arr[right-1] == a) 
            return right; // 返回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
    1216
    时间
    1000ms
    内存
    256MiB
    难度
    1
    标签
    递交数
    1
    已通过
    1
    上传者