三元组取数C++—趣学算法

Question

题目描述
给定一个三个整数数组
统计有多少个三元组满足：
1<=i,j,k<=n
a[i]<b[j]<c[k]
输入
第一行包含整数n
第二行包含n个整数a[1],a[2]等。
第三行包含n个整数b[1],b[2]等。
第四行包含n个整数c[1],c[2]等。
输出
一个整数表示答案。
样例输入 复制
3
4 1 5
9 5 5
7 6 4
样例输出 复制
8
提示
n<=10的5次幂
1<=a[i],b[i],c[i]<=10的5次幂
请问这怎么做

Answer 1

xihakonglongda 上午好☀️☀️☀️️
本答案参考ChatGPT-3.5

这道题可以使用双指针的方法来解决。我们可以考虑使用指针i遍历数组a，指针j遍历数组b，指针k遍历数组c。我们需要找到满足条件a[i]<b[j]<c[k]的三元组。

我们可以将数组a和数组b进行排序，数组c不进行排序。然后使用三个指针i、j、k来指向数组a、b、c的当前位置。初始时，i、j、k的初始位置都是数组的起始位置。

然后，我们开始遍历数组a，对于指针i指向的元素a[i]，我们在数组b中使用指针j来查找第一个大于a[i]的元素b[j]。如果找到了这样的b[j]，则在数组c中使用指针k来查找第一个大于b[j]的元素c[k]。

如果找到了满足条件的c[k]，则说明存在一个三元组满足条件a[i]<b[j]<c[k]。此时，我们可以统计满足条件的三元组的个数。

最后，我们将指针i和指针j都向后移动一位，继续寻找下一个满足条件的三元组。重复这个过程，直到遍历完整个数组a。

详细的解决方案如下：

1. 对数组a和数组b进行排序。
2. 初始化三个指针i、j、k，分别指向数组a、b、c的起始位置。
3. 初始化计数器count为0，用于统计满足条件的三元组的个数。
4. 遍历数组a，对于每个元素a[i]：
   • 在数组b中使用指针j来查找第一个大于a[i]的元素b[j]。
   • 如果找到了b[j]，则在数组c中使用指针k来查找第一个大于b[j]的元素c[k]。
   • 如果找到了满足条件的c[k]，则count加1。
   • 将指针i和指针j都向后移动一位。
5. 返回count，即满足条件的三元组的个数。

修改后的C++代码如下：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n;
    cin >> n;

    vector<int> a(n);
    vector<int> b(n);
    vector<int> c(n);

    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < n; i++) {
        cin >> b[i];
    }
    for (int i = 0; i < n; i++) {
        cin >> c[i];
    }

    sort(a.begin(), a.end());
    sort(b.begin(), b.end());

    int i = 0, j = 0, k = 0;
    int count = 0;

    while (i < n) {
        while (j < n && b[j] <= a[i]) {
            j++;
        }
        if (j == n) {
            break;
        }
        while (k < n && c[k] <= b[j]) {
            k++;
        }
        if (k == n) {
            break;
        }
        count += (n - k);
        i++;
    }

    cout << count << endl;

    return 0;
}

希望这个解决方案对你有帮助！