【题目描述】 小明在玩一个游戏,游戏是这样的,有一个 1 到 n 的排列,我们按照某种给定顺序依次删除每一个数,每删除一个数,小明将会获得这个数左边的数加上这个数右边的数这么多经验值,需要注意删除一个数后它左右两边的数就直接相连了,如果一个数左边或者右边没有数,那么从这一边获得的经验值为 0 。 现在给定最原始的排列和小明删除数字的顺序,请你帮小明算一下他最后能获得的总经验值是多少。 【输入】 第一行一个整数n(1≤n≤105) 第二行 n 个整数,p1,p2, ..., pn表示最原始的排列。 第三行 n 个整数,d1, d2, ..., dn;di表示小明第i次删除数字di。 【输出】 输出一行,包含一个整数,表示答案。 C++
时间: 2024-04-15 08:29:54 浏览: 153
CCF 201604-4 游戏题目代码_M?n_ccf考试题_
你好!对于给定的游戏规则和输入样例,可以使用C++编程语言来解决该问题。你可以按照以下步骤来实现算法:
1. 读取输入的n,最原始的排列p,和小明删除数字的顺序d。
2. 创建一个变量total_exp来保存小明最后能获得的总经验值,初始值为0。
3. 创建一个数组visited,用于标记每个数字是否已被删除,初始值为false。
4. 遍历删除顺序数组d,对于每个数字di:
- 将visited[di]设置为true,表示该数字已被删除。
- 查找di在最原始排列p中的索引index。
- 计算当前删除数字di能获得的经验值exp:
- 如果index-1不越界且visited[p[index-1]]为false,则exp加上p[index-1]。
- 如果index+1不越界且visited[p[index+1]]为false,则exp加上p[index+1]。
- 将exp加到total_exp中。
5. 输出total_exp作为答案。
以下是一个简单的C++代码示例:
```cpp
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> p(n);
for (int i = 0; i < n; i++) {
cin >> p[i];
}
vector<int> d(n);
for (int i = 0; i < n; i++) {
cin >> d[i];
}
int total_exp = 0;
vector<bool> visited(n, false);
for (int i = 0; i < n; i++) {
int di = d[i];
visited[di] = true;
int index = -1;
for (int j = 0; j < n; j++) {
if (p[j] == di) {
index = j;
break;
}
}
int exp = 0;
if (index - 1 >= 0 && !visited[p[index - 1]]) {
exp += p[index - 1];
}
if (index + 1 < n && !visited[p[index + 1]]) {
exp += p[index + 1];
}
total_exp += exp;
}
cout << total_exp << endl;
return 0;
}
```
你可以将输入样例转换为标准输入,运行该代码,即可得到输出结果。希望对你有帮助!如果还有其他问题,请随时提问。
阅读全文