侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 674 篇文章
  • 累计创建 128 个标签
  • 累计收到 20 条评论

目 录CONTENT

文章目录

【排序, 二分查找】递增三元组【蓝桥杯】

GabrielxD
2023-02-05 / 0 评论 / 0 点赞 / 99 阅读 / 621 字
温馨提示:
本文最后更新于 2023-02-05,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

1236. 递增三元组 - AcWing题库

递增三元组 - 蓝桥云课


给定三个整数数组

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

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

  1. 1i,j,kN1 \le i, j, k \le N
  2. Ai<Bj<CkA_i < B_j < C_k

输入格式

第一行包含一个整数 NN

第二行包含 NN 个整数 A1,A2,ANA_1, A_2, … A_N

第三行包含 NN 个整数 B1,B2,BNB_1, B_2, … B_N

第四行包含 NN 个整数 C1,C2,CNC_1, C_2, … C_N

输出格式

一个整数表示答案。

数据范围

1N1051 \le N \le 10^5 ,
0Ai,Bi,Ci1050 \le A_i,B_i,C_i \le 10^5

输入样例:

3
1 1 1
2 2 2
3 3 3

输出样例:

27

解题

方法一:排序 二分查找

思路

输入三个数组并排序。

在第二个数组中枚举中间数字 bb

  • 在第一个数组中二分查找严格小于 bb 的最后一个数的下标 aia_i
  • 在第三个数组中二分查找严格大于 bb 的第一个数的下标 cic_i

根据乘法原理,以 bb 为中间数字的三元组共有 aicia_i * c_i 个,那么把所有的三元组累加起来就是答案。

代码

import java.util.*;
import java.io.*;

public class _递增三元组 {
    static int n;
    static int[][] g;

    static int leftBound(int i, int x) {
        int l = 0, r = n - 1;
        while (l < r) {
            int m = l + r >> 1;
            if (g[i][m] >= x) r = m;
            else l = m + 1;
        }
        return g[i][l] >= x ? l : n;
    }

    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        n = (int) in.nval;
        g = new int[3][n];
        for (int[] arr : g) {
            for (int i = 0; i < n; ++i) {
                in.nextToken();
                arr[i] = (int) in.nval;
            }
            Arrays.sort(arr);
        }
        long cnt = 0;
        for (int i = 0; i < n; ++i) {
            int b = g[1][i];
            int ai = leftBound(0, b);
            int ci = n - leftBound(2, b + 1);
            cnt += 1L * ai * ci;
        }
        System.out.println(cnt);
    }
}
0

评论区