记录112#includebits/stdc.h using namespace std; const int N1e610; int a[N]; int n,m,q; int f_first(int x){//找到第一个下标(二分查找修改版) int l1,rn;//左右边界 int pos-1;//返回下标位置 while(lr){//满足查找 int mid(lr)/2;//中间值 if(a[mid]x){//找到了 posmid;//记录下标 rmid-1;//缩小右边界(找第一个下标) }else if(a[mid]x) rmid-1;//缩小有边界 else lmid1;//缩小左边界 } return pos;//返回下标 } int main(){ cinnm; for(int i1;in;i) cina[i]; for(int i1;im;i){ cinq; coutf_first(q) ; } return 0;//结束程序 }前言我是一名专注信奥赛CSP-J/S、NOIP的教练。如果你觉得这篇题解对你有帮助欢迎点击关注我的CSDN账号我会持续更新高质量算法解析。我深知算法思维的构建远比单纯通过题目更重要本系列题解不局限于AC代码的堆砌而是致力于拆解题目背后的逻辑链条与核心知识点备赛路上若遇瓶颈欢迎随时评论或私信我将甄选典型疑难问题通过视频讲解或撰写专项文章的形式为你提供深度答疑。题目传送门https://www.luogu.com.cn/problem/P2249突破口输入 n 个不超过 10的9次方 的单调不减的就是后面的数字不小于前面的数字非负整数 a1​,a2​,…,an​然后进行 m 次询问。对于每次询问给出一个整数 q要求输出这个数字在序列中第一次出现的编号如果没有找到的话输出 −1 。 一、题目本质与核心要求 问题重述给定一个长度为 n 的非负整数序列a[1..n]序列满足单调不减即a[i] ≤ a[i1]进行m次查询每次给一个整数q要求输出q在序列中第一次出现的下标从 1 开始若未出现输出-1✅ 关键词提炼有序数组→ 可用二分查找第一次出现→ 需要“左边界”二分多次查询→ 每次 O(log n) 比 O(n) 快得多数据量大n ≤ 1e6, m ≤ 1e5→ 必须用高效算法 样例解析输入 #1n11, m3 a [1, 3, 3, 3, 5, 7, 9, 11, 13, 15, 15] queries: q 1, 3, 6q1首次出现在位置1q3首次出现在位置2不是 3 或 4q6不存在 →-1输出1 2 -1 二、核心知识点拆解1.为什么能用二分因为数组单调不减sorted non-decreasing二分查找的前提是有序性2.普通二分 vs “找第一个出现位置”普通二分找到任意一个等于x的位置即可本题要求最左边的等于x的位置解法在找到a[mid] x后不立即返回而是继续向左搜索 这称为“lower_bound”下界问题3.时间复杂度分析每次查询O(log n)总时间O(m log n) ≈ 1e5 × log₂(1e6) ≈ 1e5 × 20 2e6 操作✅ 可接受若暴力扫描O(m × n) ≈ 1e11 ❌ 超时4.边界处理数组下标从1 开始题目要求输出从 1 编号二分初始l 1,r n未找到时返回-1代码分析#includebits/stdc.h using namespace std; const int N 1e6 10; int a[N]; // 存储序列下标从1开始 int n, m, q;N 1e6 10略大于最大 n1e6防越界全局变量自动初始化为 0int f_first(int x) { // 找 x 第一次出现的位置1-based int l 1, r n; // 搜索区间 [1, n] int pos -1; // 默认未找到while (l r) { int mid (l r) / 2; // 中点注意此处无溢出风险因 n ≤ 1e6标准二分循环条件l rif (a[mid] x) { pos mid; // 记录当前位置 r mid - 1; // 继续向左找更早的出现位置 }这是本题最关键的逻辑即使找到了x也不能停必须尝试在[l, mid-1]中找更靠左的xelse if (a[mid] x) r mid - 1; // x 在左半部分 else l mid 1; // a[mid] xx 在右半部分 } return pos; // 若从未找到pos 保持 -1 }int main() { cin n m; for (int i 1; i n; i) cin a[i]; // 读入序列1-basedfor (int i 1; i m; i) { cin q; cout f_first(q) ; } return 0; }潜在优化与注意事项问题说明IO 速度题目提示“输入输出量较大”建议加ios::sync_with_stdio(false); cin.tie(0);但原代码未加可能在极限数据下 TLEmid 计算(l r) / 2在 n ≤ 1e6 时安全lr ≤ 2e6 2³¹返回值正确处理了“未找到”情况pos初始为 -1下标一致性全程使用 1-based与题目要求一致✅ 建议优化 IO虽原代码没写但实际竞赛应加上ios::sync_with_stdio(false); cin.tie(nullptr);与其他方法对比方法时间复杂度是否可行暴力线性扫描O(m × n) ≈ 1e11❌ 超时哈希表预处理O(n m)但无法保证“第一次出现”顺序❌ 错误哈希存的是任意位置二分查找左边界O(m log n) ≈ 2e6✅ 正确高效