本文主要是介绍蓝桥杯-递增三元组(三种解法,二分, 双指针, 前缀和)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
给定三个整数数组
A=[A1,A2,…AN],
B=[B1,B2,…BN],
C=[C1,C2,…CN],
请你统计有多少个三元组 (i,j,k)
满足：
1≤i,j,k≤N
Ai<Bj<Ck
输入格式
第一行包含一个整数 N。
第二行包含 N 个整数 A1,A2,…AN。
第三行包含 N 个整数 B1,B2,…BN。
第四行包含 N 个整数 C1,C2,…CN。
输出格式
一个整数表示答案。
数据范围
1≤N≤105,
0≤Ai,Bi,Ci≤105
输入样例：
3
1 1 1
2 2 2
3 3 3
输出样例：
27
题解:
这题有五种写法~
- 超时的写法: 纯暴力和mini版的暴力
- ac的写法: 二分或者前缀和或双指针
纯暴力代码👇, 时间复杂度O(n^3)
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int a[N], b[N], c[N];
int as[N], cs[N];
int cnt[N];int main()
{int n; cin >> 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];int res = 0;for (int i = 0; i < n; i ++)for (int j = 0; j < n; j ++ )for (int k = 0; k < n; k ++){if (a[i] < b[j] && b[j] < c[k]) res ++;}cout << res << endl;return 0;
}
这里我们进行一些优化
- 我们只枚举b数组, 然后看 a 中比当前b[j]小的个数cnt1 和 c中比当前b[j]大的个数cnt2, 那么此时能跟当前b[j]组成满足题目要求的三元组的个数就是 cnt1 * cnt2
mini版的暴力👇, 时间复杂度O(n^2)
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int a[N], b[N], c[N];
int as[N], cs[N];
int cnt[N];int main()
{int n; cin >> 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];int res = 0;for (int j = 0; j < n; j ++){int cnt1 = 0, cnt2 = 0;for (int i = 0; i < n; i ++) if (a[i] < b[j]) cnt1 ++;for (int k = 0; k < n; k ++) if (c[k] > b[j]) cnt2 ++;res += cnt1 * cnt2;}cout << res << endl;return 0;
}
ac写法 -> 二分版本 时间复杂度O(nlogn)
ac代码👇
- 我们可以用二分优化mini版暴力中查找个数这个步骤
#include <bits/stdc++.h>
using namespace std;
#define int long long // int 会爆掉
const int N = 1e5 + 10;
int a[N], b[N], c[N];
int as[N], cs[N];
int cnt[N];signed main()
{int n; cin >> 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, a + n); sort(c, c + n);int res = 0;for (int j = 0; j < n; j ++){int cnt1 = 0, cnt2 = 0;int l = 0, r = n - 1;while (l < r){int mid = l + r + 1 >> 1;if (a[mid] < b[j]) l = mid; // 找到的是a小于b[j]的最后一个数的下标 (因为找到的是下标, 所有后面乘的时候 要+1)else r = mid - 1;}if (a[l] >= b[j]) cnt1 = -1; // 不满足条件的 后面+1的时候刚好0else cnt1 = l;l = 0, r = n - 1;while (l < r){int mid = l + r >> 1;if (c[mid] > b[j]) r = mid; // 找到的是c大于b[j]的第一个数的下标, 所以c中大于 b[j]的个数就是 (n - 下标)else l = mid + 1;}if (c[l] <= b[j]) cnt2 = 0; // 不满足条件的 等于0else cnt2 = n - l;res += (cnt1 + 1) * cnt2; // a c有任意一个不存在满足条件的都不能算在答案中}cout << res << endl;return 0;
}
ac写法 -> 前缀和版本 时间复杂度O(n)
ac代码👇
- 代码中的每个a,b,c之所以都 加1是因为 它们的最小值包含0, 求前缀和下标0要空出来
- as[t] 表示的是数组a中的元素小于等于t的个数的总和
- cs[t] 表示的是数组c中的元素小于等于t的个数的总和
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5 + 10;
int a[N], b[N], c[N];
int as[N], cs[N];
int cnt[N];signed main()
{int n; cin >> n;for (int i = 1; i <= n; i ++){cin >> a[i]; a[i] ++;as[a[i]] ++;}for (int i = 1; i <= n; i ++) cin >> b[i], b[i] ++;for (int i = 1; i <= n; i ++) {cin >> c[i]; c[i] ++;cs[c[i]] ++;}for (int i = 1; i <= N; i ++) as[i] += as[i - 1]; // 求前缀和for (int i = 1; i <= N; i ++) cs[i] += cs[i - 1];int res = 0;for (int j = 1; j <= n; j ++)res += as[b[j] - 1] * (cs[N - 1] - cs[b[j]]); // a 要小于b[j]所以是 as[b[j] - 1]; cs[b[j]]表示c中小于等于b[j]的元素个数, c一共有n个, 大于b[j]的就有 n - cs[b[j]].cout << res << endl;return 0;
}ac写法 ->双指针版本 时间复杂度O(n)
- 两个while循环在在整个代码运行过程中最多运行n次, 整个代码的时间复杂度是 O(n)
ac代码👇
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5 + 10;
int a[N], b[N], c[N];
int as[N], cs[N];
int cnt[N];signed main()
{int n; 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);int res = 0, ai = 1, ci = 1;for (int j = 1; j <= n; j ++){while (ai <= n && a[ai] < b[j]) ai ++; while (ci <= n && c[ci] <= b[j]) ci ++;res += (ai - 1) * (n - ci + 1);}cout << res << endl;return 0;
}
最终提交运行时间对比, 前缀和的是最快的
觉得写的不错的话, 点个赞吧~
这篇关于蓝桥杯-递增三元组(三种解法,二分, 双指针, 前缀和)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
