AcWing1236.递增三元组（蓝桥杯C++AB辅导课）

AcWing 1236. 递增三元组（蓝桥杯C++ AB辅导课）

题目传送门

#include<iostream> #include<algorithm> using namespace std; typedef long long ll; const int N = 1e5 + 10; int n; int a[N], b[N], c[N]; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n; for (int i = 1; i <= n; i ++) cin >> a[i]; for (int i = 1; i <= n; i ++) cin >> b[i]; for (int i = 1; i <= n; i ++) cin >> c[i]; sort(a + 1, a + n + 1); sort(b + 1, b + n + 1); sort(c + 1, c + n + 1); ll ans = 0; for (int i = 1, indexA = 1, indexC = 1; i <= n; i ++) { int B = b[i]; while (indexA <= n && a[indexA] < B) { indexA ++; } while (indexC <= n && c[indexC] <= B) { indexC ++; } // 按照以下例子说明 /*1 3 5 4 4 6 5 7 8*/ // 当B指针指向4时，A指针进行比对当比对到元素5时， // 发现不符合A<B，所以跳过，但这里的A指针直到了 // 下标3位置，再转到C指针进行比对，但所有的元素 // 都大于4，符合B<C，所以可以匹配的递增三元组的 // 个数是ans = (3 - 1) * (3 - 1 + 1) = 6 // 以此类推，所有三元组的个数为ans = 6 + 6 + 6 = 18 ans += (ll)(indexA - 1) * (n - indexC + 1); } cout << ans <<endl; return 0; }