题目： 给定三个整数数组 A = [A1, A2, … AN], B = [B1, B2, … BN], C = [C1, C2, … CN]， 请你统计有多少个三元组(i, j, k) 满足： 1. 1 <= i, j, k <= N 2. Ai < Bj < Ck 【输入格式】 第一行包含一个整数N。 第二行包含N个整数A1, A2, ... AN。 第三行包含N个整数B1, B2, ... BN。 第四行包含N个整数C1, C2, ... CN。
对于30%的数据，1 <= N <= 100 对于60%的数据，1 <= N <= 1000 对于100%的数据，1 <= N <= 100000 0 <= Ai, Bi, Ci <= 100000
【输出格式】 一个整数表示答案 解题思路： 关键是数组b，从头开始遍历，在a数组中找到比b[j]小的元素个数(x)，在c组中找到比b[j]大的元素个数(y)， 所以 a[i] < b[j] < c[k]的元组个数就为 x * y;
代码：
#include <iostream> #include <algorithm> using namespace std; int main() { int n; cin >> n; int *a = new int[n]; int *b = new int[n]; int *c = new int[n]; int i; //输入 for (i = 0; i < n; i++) cin >> a[i]; for (i = 0; i < n; i++) cin >> b[i]; for (i = 0; i < n; i++) cin >> c[i]; sort(a, a + n);//默认是从小到大 sort(b, b + n); sort(c, c + n); int sum = 0; for (i = 0; i < n; i++) { int x = lower_bound(a, a + n, b[i]) - a; /*lower_bound()函数头文件：algorithm，意思是在a[0]到a[n - 1]中找到比b[i]小的元素地址，减去 数组的初始位置a后，就得到比b[i]小的首个元素下标，而数组下标是从0开始的，所以x就是a中比b[i] 小的元素个数*/ int y = n - (upper_bound(c, c + n, b[i]) - c); sum += x * y; } cout << sum << endl; return 0; }
