【洛谷 P2249】【深基13.例1】查找(向量+二分查找+循环)

简介: 该题目要求在一个单调不减的整数序列中查找给定数值首次出现的位置,输出-1表示未找到。给定$n$个整数和$m$次询问,需对每个询问使用二分查找法高效解答。样例输入为11个数和3次询问,输出分别为1、2和-1。代码中定义了快速读取整数的函数`read()`,并使用二分查找`search()`实现。在主函数中,先读取序列和询问,然后对每个询问进行二分查找并输出结果。

【深基13.例1】查找

题目描述

输入 $n$ 个不超过 $10^9$ 的单调不减的(就是后面的数字不小于前面的数字)非负整数 $a_1,a2,\dots,a{n}$,然后进行 $m$ 次询问。对于每次询问,给出一个整数 $q$,要求输出这个数字在序列中第一次出现的编号,如果没有找到的话输出 $-1$ 。

输入格式

第一行 $2$ 个整数 $n$ 和 $m$,表示数字个数和询问次数。

第二行 $n$ 个整数,表示这些待查询的数字。

第三行 $m$ 个整数,表示询问这些数字的编号,从 $1$ 开始编号。

输出格式

输出一行,$m$ 个整数,以空格隔开,表示答案。

样例 #1

样例输入 #1

11 3
1 3 3 3 5 7 9 11 13 15 15
1 3 6

样例输出 #1

1 2 -1

提示

数据保证,$1 \leq n \leq 10^6$,$0 \leq a_i,q \leq 10^9$,$1 \leq m \leq 10^5$

本题输入输出量较大,请使用较快的 IO 方式。

思路

数据量很大,需要优化读入。通过循环进行二分查找。

AC代码

#include <iostream>
#define AUTHOR "HEX9CF"
using namespace std;

const int maxn = 1000005;

int n, m, q;
int a[maxn];

int read(){
   
    char ch;
    int x = 0;
    while((ch < '0' || ch > '9')){
   
        ch = getchar();
    }
    while(!(ch < '0' || ch > '9')){
   
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x;
}

int search(int a[], int u, int v, int q){
   
    while (u < v)
    {
   
        int mid = (u + v) / 2;
        if (q <= a[mid])
        {
   
            v = mid;
        }
        else
        {
   
            u = mid + 1;
        }
    }
    if (a[u] == q)
    {
   
        return u + 1;
    }
    else
    {
   
        return -1;
    }
}

int main()
{
   
    n = read();
    m = read();
    for (int i = 0; i < n; i++)
    {
   
        a[i] = read();
    }
    for (int i = 0; i < m; i++)
    {
   
        if(i){
   
            putchar(' ');
        }
        q = read();
        cout << search(a, 0, n - 1, q);
    }
    return 0;
}
目录
相关文章
|
Serverless 索引 Python
统计学中基础概念说明(二)
统计学中基础概念说明(二)
统计学中基础概念说明(二)
|
调度 弹性计算 存储
拆解超算上云的障碍,阿里云用了这三招|E-HPC如何改变云超算?
2019年阿里云上海峰会,由阿里云资深技术专家何万青带来以“阿里云超算E-HPC平台”为题的演讲。本文内容包括了HPC概念及发展趋势,面向“大计算”设计的弹性基础设施,客户应用云上优化,着重介绍了E-HPC自动伸缩,闲时计算方案与混合云,数据全流程可视化以及HPC工作流与数据迁移等。
2082 0
|
12月前
|
IDE 关系型数据库 MySQL
Django学习一:创建Django框架,介绍Django的项目结构和开发逻辑。创建应用,编写主包和应用中的helloworld
这篇文章是关于如何创建一个Django框架,介绍Django的项目结构和开发逻辑,并指导如何创建应用和编写“Hello, World!”程序的教程。
696 3
Django学习一:创建Django框架,介绍Django的项目结构和开发逻辑。创建应用,编写主包和应用中的helloworld
【洛谷 P1036】[NOIP2002 普及组] 选数 题解(深度优先搜索+判断质数+枚举子集)
**NOIP2002普及组选数问题**:给定$n$个整数和一个整数$k$,需找出所有$k$个数的组合,计算它们的和为素数的种类数。输入包含$n$和$k$,以及$n$个整数;输出是符合条件的组合数。例如,对于输入`4 3`和数组`[3, 7, 12, 19]`,输出为`1`。代码使用递归枚举子集并检查质数的方法。
397 0
|
11月前
|
存储 安全 大数据
大数据隐私保护:用户数据的安全之道
【10月更文挑战第31天】在大数据时代,数据的价值日益凸显,但用户隐私保护问题也愈发严峻。本文探讨了大数据隐私保护的重要性、面临的挑战及有效解决方案,旨在为企业和社会提供用户数据安全的指导。通过加强透明度、采用加密技术、实施数据最小化原则、加强访问控制、采用隐私保护技术和提升用户意识,共同推动大数据隐私保护的发展。
1119 3
|
人工智能 自然语言处理 数据挖掘
【通义】AI视界|性能超越GPT-4o?最强大的开源AI模型来了……
本文介绍了五项最新AI技术动态,包括性能超越GPT-4o的开源AI模型Reflection70B、智谱清言App限时免费的视频通话功能、哈佛医学院研发的癌症诊断AI模型CHIEF、Replit推出的AI编程助手,以及英特尔与日本AIST合作设立的芯片制造研发中心。这些进展展示了AI领域的快速创新与广泛应用。更多详情,请访问通义官网体验。
|
关系型数据库 MySQL 大数据
教你使用Python玩转MySQL数据库,大数据导入不再是难题!
教你使用Python玩转MySQL数据库,大数据导入不再是难题!
269 1
|
关系型数据库 MySQL 应用服务中间件
使用docker搭建nacos集群
使用docker搭建nacos集群
1922 1
使用docker搭建nacos集群
|
前端开发 关系型数据库 MySQL
SpringBoot-----从前端更新数据到MySql数据库
SpringBoot-----从前端更新数据到MySql数据库
163 1
|
存储 弹性计算 Serverless
什么是阿里云FPGA云服务器?FPGA云服务器产品优势及应用场景介绍
FPGA云服务器是阿里云提供的实例规格,融合现场可编程门阵列的低延迟硬件加速与弹性资源。FaaS平台简化了FPGA开发,提供统一硬件、开发环境和丰富的IP生态。特性包括硬件虚拟化、联合仿真和动态互联配置。产品计费与ECS一致,支持多种计费模式。优势在于分钟级交付、高性能加速、经济性价比和设计复用。应用广泛,如视频转码、人工智能、基因测序等。FPGA云服务器通过FPGA镜像、OSS服务等工具进行管理。
什么是阿里云FPGA云服务器?FPGA云服务器产品优势及应用场景介绍