首页程序设计基础C6 - 2024级程序设计基础第六次上机赛
时间限制 空间限制
1000 ms 10240 KB

注意内存限制，该内存限制下无法申请千万级别的数组。

# 题目描述

现在有 nn 只水獭从低到高站成一排。Moca 希望每次能找到不低于某身高 hh 的第一只水獭的编号（编号从 11 开始），请你编写一个程序完成这个任务。

# 输入格式

第一行两个正整数 nn 和 mm，其中 nn 表示小水獭的个数，保证 1≤n≤5×1051 \le n \le 5 \times 10^5；mm 表示接下来询问的次数，保证 1≤m≤5×1051 \le m \le 5 \times 10^5​。

接下来一行，输入 nn 个正整数，第 ii 个正整数表示第 ii 只小水獭的身高 aia_i，保证 1≤ai≤1071 \le a_i \le 10^7，输入的 aia_i 单调不减。

接下来 mm 行，每行一个正整数 hih_i，表示要查找的值，保证 1≤hi≤1071 \le h_i \le 10^7。

# 输出格式

输出 mm 行，对每次询问，输出对应的不低于对应身高 hh 的第一只水獭的编号；如果不存在这样的水獭输出 -1 。

# 样例输入

5 5
2 7 10 10 13
1
8
10
12
14

# 样例输出

1
3
3
5
-1

# 题解：二分

二分查找板子题。参考代码：

#include <stdio.h>
int n, m, a[500010];
int main()
{
    // freopen("F.in", "r", stdin);
    // freopen("F.out", "w", stdout);
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++ i)
        scanf("%d", &a[i]);
    
    while (m -- )
    {
        int h;
        scanf("%d", &h);
        if (h > a[n])
        {
            puts("-1");
            continue;
        }
        int l = 1, r = n;
        while (l < r)
        {
            int mid = (l + r) >> 1;
            if (h <= a[mid])
                r = mid;
            else
                l = mid + 1;
        }
        printf("%d\n", l);
    }
    return 0;
}