能否用C++完成这道题目:小明有 nn 张上面有不同数字的纸牌,他用了很长一段时间才将这些纸牌从左到右按升序排成了一排,并在在每个纸牌的下面写上了一个位置编号,编号是从左到右从 11 开始的。可是一只调皮的小狗把他的纸牌全部都弄乱了,现在小明需要你的帮助,他一共会问你 kk 次,每次问你一张数字纸牌,你需要正确回答他该纸牌原先所在的位置编号。 输入 第一行两个正整数 nn 和 kk; 1 \leq n \leq 2\times10^61≤n≤2×10 6 ,1 \leq k \leq 10^51≤k≤10 5 。 第二行是 nn 个正整数,表示被小狗弄乱的纸牌上的数字 a_ia i ;1 \leq a_i \leq n\times51≤a i ≤n×5 第三行是 kk 个正整数,表示小明的每一次询问的数字。 输出 输出一共有 kk 行,对于小明的每次询问,输出一行正确的位置编号。
时间: 2024-04-15 12:24:19 浏览: 90
是的,我可以用C++编写一个解决该问题的程序。下面是代码示例:
```cpp
#include <iostream>
#include <vector>
#include <unordered_map>
int main() {
int n, k;
std::cin >> n >> k;
std::vector<int> cards(n);
for (int i = 0; i < n; i++) {
std::cin >> cards[i];
}
std::unordered_map<int, int> positions;
for (int i = 0; i < n; i++) {
positions[cards[i]] = i + 1;
}
for (int i = 0; i < k; i++) {
int query;
std::cin >> query;
std::cout << positions[query] << std::endl;
}
return 0;
}
```
这段代码首先读取纸牌的数量n和询问次数k。然后,它读取n个数字表示纸牌上的数字,并将每个数字与其原先的位置编号存储在一个unordered_map中。最后,根据小明的每次询问,我们从unordered_map中查找相应数字的位置编号并输出。
请注意,由于纸牌的数字范围是1到n * 5,我们可以使用unordered_map来实现O(1)时间复杂度的查找操作。
阅读全文