【题目描述】 小明在玩一个游戏,游戏是这样的,有一个 1 到 n 的排列,我们按照某种给定顺序依次删除每一个数,每删除一个数,小明将会获得这个数左边的数加上这个数右边的数这么多经验值,需要注意删除一个数后它左右两边的数就直接相连了,如果一个数左边或者右边没有数,那么从这一边获得的经验值为 0 。 现在给定最原始的排列和小明删除数字的顺序,请你帮小明算一下他最后能获得的总经验值是多少。 【输入】 第一行一个整数n (1≤n≤105 ) 第二行 n 个整数,p1 ,p2 , ..., pn 表示最原始的排列。 第三行 n 个整数,d1 , d2 , ..., dn ;di 表示小明第i 次删除数字di 。 【输出】 输出一行,包含一个整数,表示答案。 【输入样例】 3 1 2 3 3 1 2 【输出样例】 4C++
时间: 2024-04-13 22:28:47 浏览: 381
题目描述中给出了一个游戏的情景,有一个 1 到 n 的排列,按照给定的顺序逐个删除每个数。每次删除一个数时,获得的经验值等于该数左边的数加上右边的数。需要注意,删除一个数后,左右两边的数直接相连,如果某一边没有数,则获得的经验值为 0。现在要求计算最后能获得的总经验值。
要解决这个问题,我们可以按照给定的顺序逐个删除数字,并累加经验值。具体做法如下:
1. 定义一个变量 total_exp,初始化为 0,用于保存总经验值。
2. 遍历给定的删除顺序列表。
- 在每一次循环中,找到当前要删除的数字在原始排列中的位置 index。
- 如果 index > 0,则将原始排列中 index-1 的数加到 total_exp 中。
- 如果 index < n-1,则将原始排列中 index+1 的数加到 total_exp 中。
- 将当前要删除的数字从原始排列中删除。
3. 输出 total_exp。
下面是使用 C++ 编写的代码实现上述算法:
```cpp
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> original(n);
for (int i = 0; i < n; i++) {
cin >> original[i];
}
vector<int> deletion(n);
for (int i = 0; i < n; i++) {
cin >> deletion[i];
}
long long total_exp = 0;
for (int i = 0; i < n; i++) {
int index = 0;
while (original[index] != deletion[i]) {
index++;
}
if (index > 0) {
total_exp += original[index - 1];
}
if (index < n - 1) {
total_exp += original[index + 1];
}
original.erase(original.begin() + index);
}
cout << total_exp << endl;
return 0;
}
```
这段代码首先读取输入的 n,然后读取最原始的排列和删除顺序,分别存储在 `original` 和 `deletion` 数组中。
接下来,定义一个变量 `total_exp`,初始化为 0,用于保存总经验值。然后,使用循环遍历删除顺序列表,找到当前要删除的数字在原始排列中的位置,并根据位置是否在边界上累加经验值。最后,将当前要删除的数字从原始排列中删除。
最后,输出 `total_exp`。
希望对你有帮助!如果你有任何问题,请随时提问。
阅读全文
相关推荐
















