• 算法-递增三元组


    题目描述

    给定三个整数数组

    A = [ A 1 , A 2 , … A N ] , A=[A_1,A_2,…A_N], A=[A1​,A2​,…AN​],
    B = [ B 1 , B 2 , … B N ] , B=[B_1,B_2,…B_N], B=[B1​,B2​,…BN​],
    C = [ C 1 , C 2 , … C N ] , C=[C_1,C_2,…C_N], C=[C1​,C2​,…CN​],

    请你统计有多少个三元组 ( i , j , k ) (i,j,k) (i,j,k) 满足:

    1. 1 ≤ i , j , k ≤ N 1≤i,j,k≤N 1≤i,j,k≤N
    2. A i < B j < C k Ai

    输入格式

    第一行包含一个整数 N N N。

    第二行包含 N N N 个整数 A 1 , A 2 , … A N 。 A_1,A_2,…A_N。 A1​,A2​,…AN​。

    第三行包含 N N N 个整数 B 1 , B 2 , … B N 。 B_1,B_2,…B_N。 B1​,B2​,…BN​。

    第四行包含 N N N 个整数 C 1 , C 2 , … C N 。 C_1,C_2,…C_N。 C1​,C2​,…CN​。

    输出格式

    一个整数表示答案。

    数据范围

    1 ≤ N ≤ 105 , 1≤N≤105, 1≤N≤105,
    0 ≤ A i , B i , C i ≤ 105 0≤Ai,Bi,Ci≤105 0≤Ai,Bi,Ci≤105

    输入样例1:

    1. 3
    2. 1 1 1
    3. 2 2 2
    4. 3 3 3

    输出样例1:

    27
    

    思路

    我自己想的时候是枚举 a a a 组中的每一个元素,然后二分出 b b b 和 c c c 中的边界点,然后相乘。但是自己想错了, 因为 b b b 和 c c c 有关系,所以不能直接相乘。

    那么其实可以枚举 b b b 中的每一个点,再根据 b i b_i bi​ 找到 a , c a,c a,c 中小于 b i bi bi 的数 和 大于 b i bi bi 的数 ,因为如此分, a a a 和 c c c 就是独立存在,可以用乘法原理

    如果暴力解决,那么必然是需要 O ( n 3 ) O(n^3) O(n3)的复杂度枚举三个点再判断其大小,必定超时

    所以可以想办法优化,可以看出我们找小于和大于 b i b_i bi​ 的数时,可以

    • 排序 + 二分找到边界点
    • 前缀和求小于 b i b_i bi​ 的个数和 大于 b i b_i bi​ 的个数
    • 双指针

    排序 + 二分

    对三个数组排序,枚举 b b b 的每一个点,然后二分出 a a a 中小于 b i b_i bi​ 的第一个数和 b b b 中大于 b i b_i bi​ 的第一个数,算出个数相乘即可

    时间复杂度

    O ( n l o g n ) O(nlogn) O(nlogn)

    C++ 代码

    1. #include <iostream>
    2. #include <algorithm>
    3. using namespace std;
    4. typedef long long LL;
    5. const int N = 100010;
    6. int q[3][N];
    7. int n;
    8. int lowbound(int i,int x) {
    9. int l = 0, r = n - 1;
    10. while(l < r) {
    11. int mid = l + r + 1>> 1;
    12. if(q[i][mid] < x) l = mid;
    13. else r = mid - 1;
    14. }
    15. if(q[i][l] >= x) l = -1;
    16. return l;
    17. }
    18. int upbound(int i,int x) {
    19. int l = 0, r = n - 1;
    20. while(l < r) {
    21. int mid = l + r >> 1;
    22. if(q[i][mid] > x) r = mid;
    23. else l = mid + 1;
    24. }
    25. if(q[i][r] <= x) r = n;
    26. return r;
    27. }
    28. int main()
    29. {
    30. cin >> n;
    31. for(int i = 0;i < 3;i ++) {
    32. for(int j = 0;j < n;j ++) scanf("%d",&q[i][j]);
    33. sort(q[i],q[i] + n);
    34. }
    35. LL res = 0;
    36. for(int i = 0;i < n;i ++) {
    37. int x = q[1][i];
    38. int l1 = lowbound(0,x);
    39. int l2 = upbound(2,x);
    40. res += (LL)(l1 + 1) * (n - l2);
    41. }
    42. cout << res << endl;
    43. return 0;
    44. }

    前缀和

    时间复杂度

    O ( N ) O(N) O(N)

    C++ 代码

    1. #include <cstring>
    2. #include <iostream>
    3. using namespace std;
    4. typedef long long LL;
    5. const int N = 100010;
    6. int a[N], b[N], c[N];
    7. int as[N]; // as[i]表示小于b[i]的数的个数
    8. int cs[N]; // cs[i]表示大于b[i]的数的个数
    9. int cnt[N], s[N];
    10. int n;
    11. int main()
    12. {
    13. scanf("%d",&n);
    14. for(int i = 0;i < n;i ++) scanf("%d",&a[i]), a[i] ++;
    15. for(int i = 0;i < n;i ++) scanf("%d",&b[i]), b[i] ++;
    16. for(int i = 0;i < n;i ++) scanf("%d",&c[i]), c[i] ++;
    17. for(int i = 0;i < n;i ++) cnt[a[i]] ++;
    18. for(int i = 1;i < N;i ++) s[i] = s[i - 1] + cnt[i];
    19. //as
    20. for(int i = 0;i < n;i ++) as[i] = s[b[i] - 1];
    21. memset(cnt, 0, sizeof cnt);
    22. memset(s, 0, sizeof s);
    23. // 求cs
    24. for(int i = 0;i < n;i ++) cnt[c[i]] ++;
    25. for(int i = 1;i < N;i ++) s[i] = s[i - 1] + cnt[i];
    26. for(int i = 0;i < n;i ++) cs[i] = s[N - 1] - s[b[i]];
    27. LL res = 0;
    28. for(int i = 0;i < n;i ++) res += (LL) as[i] * cs[i];
    29. cout << res << endl;
    30. return 0;
    31. }
  • 相关阅读:
    OpenSSL安装过程总结
    数字人扫描对虚拟人三维动画宣传片制作有何作用?
    vue2 顶象 安全 验证码的使用
    uniapp——uniapp如何打包成安卓——自有证书
    java计算机毕业设计共享充电宝管理系统演示录像2021源码+mysql数据库+系统+lw文档+部署
    字节跳动端智能工程链路 Pitaya 的架构设计
    linux中的input设备(转)
    浅谈为什么多态只能是指针或引用
    港科夜闻|香港特首李家超,教育局局长蔡若莲与创新科技及工业局局长孙东亲临香港科大,聆听青年才俊之声...
    初始百度地图API
  • 原文地址:https://blog.csdn.net/mooczhimahu/article/details/126556539