一天,王老师在仓库里找到了三个序列,分别是 A,B,C,它们的长度 一样长,N 是它们的长度。 王老师仔细对序列的每一个元素进行了观察,然后他思考出了一个问题。 这三个整数序列他称作 A = (A 1 , A 2 , …, A N ), B = (B 1 , B 2 , …, B N ), C = (C 1 , C 2 , …, C N ) 如果存在两个下标 i , j 使得整数对 (i,j) 满足 A[i]=B[C[j]] ,那么王老师的满意度就会加 1 , 现在王老师知道每个序列里的数字,请问他最后的满意度是多少? 输入格式 输入第一行有 1 个正整数 N。 接下来从第二行到第四行依次是 A,B,C 序列的元素。 A 1 A 2 … A N B 1 B 2 … B N C 1 C 2 … C N 输出格式 输出一个整数即王老师的满意度 样例输入 1 3 1 2 2 3 1 2 2 3 2 样例输出 1 4 样例输入 2 4 1 1 1 1 1 1 1 1 1 2 3 4 样例输出 2 16 提示/说明 样例解释 对于样例一:以下 4 个整数对满足条件 (1,1),(1,3),(2,2),(3,2)(1,1),(1,3),(2,2),(3,2) 对于样例二: 所有整数对都满足条件 数据范围 对于 60% 的数据 1≤N≤10 3 ;1≤A i ,B i ,C i ≤N; 对于 100% 的数据 1≤N≤10 5 ;1≤A i ,B i ,C i ≤N;不要用STL
时间: 2025-03-08 21:06:02 浏览: 100
<<
要计算王老师的满意度,我们需要检查所有可能的 `(i, j)` 对,并统计满足 `A[i] == B[C[j]]` 条件的数量。由于不能使用 STL(标准模板库),我们将手动编写必要的逻辑来解决问题。
### 解决方案步骤:
1. **读取输入**:
- 首先读取序列的长度 `N`。
- 接下来分别读取三个数组 `A`, `B`, 和 `C`。
2. **初始化计数器**:
- 使用一个变量 `count` 来记录满足条件的次数,初始值为 0。
3. **双重循环遍历**:
- 使用两层嵌套的 for 循环来枚举所有的 `(i, j)` 对。
- 在内层循环中,根据公式 `A[i] == B[C[j]]` 进行判断并更新计数器。
4. **输出结果**:
- 最后将计数器的结果作为答案进行输出。
下面是具体的 C++ 实现代码:
```cpp
#include <iostream>
using namespace std;
int main() {
int N;
cin >> N;
// 定义三个数组用于存储 A、B、C 序列的数据
int* A = new int[N];
int* B = new int[N];
int* C = new int[N];
// 输入序列 A 的元素
for (int i = 0; i < N; ++i) {
cin >> A[i];
}
// 输入序列 B 的元素
for (int i = 0; i < N; ++i) {
cin >> B[i];
}
// 输入序列 C 的元素
for (int i = 0; i < N; ++i) {
cin >> C[i];
}
int count = 0;
// 双重循环遍历所有可能的 (i, j) 组合
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
if (A[i] == B[C[j]-1]) { // 注意 C 中的索引是从 1 开始,所以减 1
++count;
}
}
}
cout << count << endl;
// 释放动态分配的空间
delete[] A;
delete[] B;
delete[] C;
return 0;
}
```
### 关键点解释:
- **内存管理**:为了处理较大的数据量 (`N <= 10^5`),我们使用了动态数组来进行存储。同时,在程序结束时记得释放这些动态分配的内存空间,避免内存泄漏。
- **边界调整**:题目中的描述提到序列 `C` 包含的是从 1 到 N 的整数,因此当我们访问 `B[C[j]]` 时需要注意转换成基于零的索引形式,即 `B[C[j]-1]`。
### 时间复杂度分析:
该算法的时间复杂度是 O(N²),因为有两个嵌套的for循环,这在给定的数据范围内是可以接受的性能表现。
阅读全文