企业官网建设流程全解析

P1918 保龄球

算法题思路分享

题目描述

DL 算缘分算得很烦闷，所以常常到体育馆去打保龄球解闷。因为他保龄球已经打了几十年了，所以技术上不成问题，于是他就想玩点新花招。

DL 的视力真的很不错，竟然能够数清楚在他前方十米左右每个位置的瓶子的数量。他突然发现这是一个炫耀自己好视力的借口——他看清远方瓶子的个数后从某个位置发球，这样就能打倒一定数量的瓶子。

1. ◯ ◯ ◯ \bigcirc \bigcirc \bigcirc◯◯◯

2. ◯ ◯ ◯ ◯ \bigcirc \bigcirc \bigcirc\ \bigcirc◯◯◯◯

3. ◯ \bigcirc◯

4. ◯ ◯ \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

输入 #1

5 1 2 4 3 5 2 4 7

输出 #1

3 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。

解题思路

1. 题目大意：给定 n 个发球位置，在第 i 个发球位置上有若干个瓶子，并且各个位置上的瓶子数量都互不相同。在某个位置发球时，能打倒的瓶子数量刚好等于该位置的瓶子数。接下来有 q 次询问，每次给出一个整数 m，表示想打倒的瓶子数，要求输出瓶子数刚好为 m 的位置编号，位置从 1 开始数。若不存在瓶子数等于 m 的位置，则输出 0。
2. 常规思路：使用暴力循环解决此题。n 和 Q 最大都是 100000，100000 次询问 × 每次最多扫 100000 个位置 = 10¹⁰ 次操作，必然超时，所以要寻求更快的解法。
3. 进阶思路：观察此题：任务是对每个 m，查找瓶子数等于 m 的位置编号。由于题目保证各位置的瓶子数互不相同，可以建立“瓶子数 → 位置编号”的对应关系，用 map 存储并查询，这是本题的优解之一。本题属于查找题，用映射解决。 为什么不用数组直接存？ 若用 arr[aᵢ] = i 建立对应关系，数组大小需要按 aᵢ 的最大值开到 10⁹，内存直接爆炸。map 只为实际出现过的瓶子数建立条目，最多 n 条，内存毫无压力。
4. 实现步骤：（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⁶ 次操作，远低于时限。
5. 代码实现如下：

// P1918 保龄球#include<bits/stdc++.h>usingnamespacestd;usingll=longlong;intmain(){// 位置数intn;cin>>n;// 存储 瓶子数 -> 位置编号 的对应关系map<ll,ll>pos;// 逐个读入每个位置的瓶子数，记入表中for(inti=1;i<=n;i++){// 该位置的瓶子数ll cnt;cin>>cnt;// 瓶子数 cnt 对应位置 i，位置从 1 数起pos[cnt]=i;}// 发球次数intq;cin>>q;// 处理每次询问while(q--){// 想打倒的瓶子数ll m;cin>>m;// 在表中查找瓶子数等于 m 的记录autoit=pos.find(m);if(it!=pos.end()){// 找到了，输出对应的位置编号cout<<it->second<<'\n';}else{// 没找到，输出 0cout<<0<<'\n';}}return0;}