P1918 保龄球算法题思路分享文章目录P1918 保龄球题目描述输入格式输出格式输入输出样例 #1输入 #1输出 #1说明/提示解题思路题目描述DL 算缘分算得很烦闷所以常常到体育馆去打保龄球解闷。因为他保龄球已经打了几十年了所以技术上不成问题于是他就想玩点新花招。DL 的视力真的很不错竟然能够数清楚在他前方十米左右每个位置的瓶子的数量。他突然发现这是一个炫耀自己好视力的借口——他看清远方瓶子的个数后从某个位置发球这样就能打倒一定数量的瓶子。◯ ◯ ◯ \bigcirc \bigcirc \bigcirc◯◯◯◯ ◯ ◯ ◯ \bigcirc \bigcirc \bigcirc\ \bigcirc◯◯◯◯◯ \bigcirc◯◯ ◯ \bigcirc\ \bigcirc◯◯如上图每个 “◯ \bigcirc◯” 代表一个瓶子。如果 DL 想要打倒3 33个瓶子就在1 11位置发球想要打倒4 44个瓶子就在2 22位置发球。现在他想要打倒m mm个瓶子。他告诉你每个位置的瓶子数请你给他一个发球位置。输入格式第一行包含一个正整数n nn表示位置数。第二行包含n nn个正整数a i a_iai​表示第i ii个位置的瓶子数保证各个位置的瓶子数不同。第三行包含一个正整数Q QQ表示 DL 发球的次数。第四行至文件末尾每行包含一个正整数m mm表示 DL 需要打倒m mm个瓶子。输出格式共Q QQ行。每行包含一个整数第i ii行的整数表示 DL 第i ii次的发球位置。若无解则输出0 00。输入输出样例 #1输入 #15 1 2 4 3 5 2 4 7输出 #13 0说明/提示【数据范围】对于50 % 50\%50%的数据1 ≤ n , Q ≤ 1000 , 1 ≤ a i , m ≤ 10 5 1 \leq n, Q \leq 1000, 1 \leq a_i, m \leq 10^51≤n,Q≤1000,1≤ai​,m≤105。对于100 % 100\%100%的数据1 ≤ n , Q ≤ 100000 , 1 ≤ a i , m ≤ 10 9 1 \leq n,Q \leq 100000, 1 \leq a_i, m \leq 10^91≤n,Q≤100000,1≤ai​,m≤109。解题思路题目大意给定 n 个发球位置在第 i 个发球位置上有若干个瓶子并且各个位置上的瓶子数量都互不相同。在某个位置发球时能打倒的瓶子数量刚好等于该位置的瓶子数。接下来有 q 次询问每次给出一个整数 m表示想打倒的瓶子数要求输出瓶子数刚好为 m 的位置编号位置从 1 开始数。若不存在瓶子数等于 m 的位置则输出 0。常规思路使用暴力循环解决此题。n 和 Q 最大都是 100000100000 次询问 × 每次最多扫 100000 个位置 10¹⁰ 次操作必然超时所以要寻求更快的解法。进阶思路观察此题任务是对每个 m查找瓶子数等于 m 的位置编号。由于题目保证各位置的瓶子数互不相同可以建立“瓶子数 → 位置编号”的对应关系用 map 存储并查询这是本题的优解之一。本题属于查找题用映射解决。 为什么不用数组直接存 若用 arr[aᵢ] i 建立对应关系数组大小需要按 aᵢ 的最大值开到 10⁹内存直接爆炸。map 只为实际出现过的瓶子数建立条目最多 n 条内存毫无压力。实现步骤1第一步先读入 n循环 n 次将每个位置的瓶子数作为 key、位置编号作为 value 存入 map。2第二步循环 q 次每次把输入的 m 作为 key 在表中查找找到就输出对应的 value也就是位置编号找不到就输出 0。 时间复杂度建表 O(n log n)每次查询 O(log n)总计 O((n q) log n)约 3.4×10⁶ 次操作远低于时限。代码实现如下// P1918 保龄球#includebits/stdc.husingnamespacestd;usinglllonglong;intmain(){// 位置数intn;cinn;// 存储 瓶子数 - 位置编号 的对应关系mapll,llpos;// 逐个读入每个位置的瓶子数记入表中for(inti1;in;i){// 该位置的瓶子数ll cnt;cincnt;// 瓶子数 cnt 对应位置 i位置从 1 数起pos[cnt]i;}// 发球次数intq;cinq;// 处理每次询问while(q--){// 想打倒的瓶子数ll m;cinm;// 在表中查找瓶子数等于 m 的记录autoitpos.find(m);if(it!pos.end()){// 找到了输出对应的位置编号coutit-second\n;}else{// 没找到输出 0cout0\n;}}return0;}