AcWing 1236. 递增三元组 (flag + 前缀和

更新时间:2023-04-04 06:45:56 阅读：评论：0

1236. 递增三元组

解题思路

最开始想到3重循环枚举三个数组，然后最内层用条件语句判断一下即可，但是数据范围为 1 0 5 10^5 105，三重循环肯定会超时那么这道题很可能需要的算法复杂度为 O ( n ) O(n) O(n)或 O ( n l o g n ) O(nlogn) O(nlogn)，所以只能枚举一个数组，那么枚举哪一个呢？根据题目来看，要求 A i < B j < C k A_i<B_j<C_k Ai<Bj<Ck，那么就来枚举B数组此时我们只需要找到A数组中所有小于 B j B_j Bj的数和C数组中所有大于 B j B_j Bj的数，然后将这两个数乘起来就是ans如何找到A数组中所有小于 B j B_j Bj的数和C数组中所有大于 B j B_j Bj的数且在遍历B数组的for循环内部的时间复杂度要低于O(n)方法一：flag + 前缀和方法二：排序 + 二分方法三：滑动窗口

方法一：flag + 前缀和 O(n)

思路：

计数排序思想：先初始化flag数组用来记录a数组每个数出现的次数计算flag数组的前缀和数组 s[n]，那么 s[i] 就表示从a数组中所有取值在 [0, i] 区间内的元素个数那么计数 a数组中所有小于 b[j] 的数就相当于求a数组中取值在 [0, b[j] – 1] 区间内的元素个数，即求s[b[j] – 1]，b数组同理

import java.util.*;import java.io.*;import java.math.*;class Main {     BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));    String sp[];        int N = 100010;    int[] a = new int[N], b = new int[N], c = new int[N];    int n;        int[] flag_a 那一缕阳光= new int[N];    int[] s_flag_a = new int[N];        int[] flag_c = new int[N];    int[] s_flag_c = new int[N];     void run() throws Exception {         sp = reader.readLine().split(" ");        n = Integer.parInt(sp[0]);        sp = reader.readLine().split(" ");        for (int i = 0; i < n; i++) {             a[i] = Integer.parInt(sp[i]);        }        sp = reader.readLine().split(" ");        for (int i = 0; i < n; i++) {             b[i] = Integer.parInt(sp[i]);        }        sp = reader.readLine().split(" ");        for (int i = 0; i < n; i++) {             c[i] = Integer.parInt(sp[i]);        }                // 用a数组初始化flag_a数组        for (int i = 0; i < n叶传萍; i++) {             flag英文句子翻译_a[a[i]]++;            flag_c[c[i]]++;        }                s_flag_a[0] = flag_a[0];        s_flag_c[0] = flag_c[0];                // 得到flag_a数组和flag_c数组的前缀和数组        for (int i = 1; i < N; i++) {             s_flag_a[i] = s_flag_a[i - 1] + flag_a[i];            s_flag_c[i] = s_flag_c[i - 1] + flag_c[i];        }                BigInteger cnt = new BigInteger("0");        // 遍历b数组        for (int i = 0; i < n; i++) {             BigInteger cnt_a = new BigInteger(String.valueOf(b[i] - 1 < 0 ? 0 : s_flag_a[b[i] - 1]));            BigInteger cnt_c = new BigInteger(String.valueOf(n - s_flag_c[b[i]]));            cnt = cnt.add(cnt_a.multiply(cnt_c));        }                System.out.println(cnt);    }    public static void main(String[] args) throws Exception {         new Main().run();    }}

方法二：排序 + 二分 O(nlogn)

注意：

二分的条件必须为：a数组和b数组中有一部分大于b[i]和小于b[i]的数，需要特判一下全小于等于或者全大于等于b[i]的情况，否则二分会出错Arrays.sort(int[] arr, int startIndex, int endIndex)时需要注意的是[startIndex, endIndex)，和substring一样N的数据范围为 1 0 5 10^5 105，那么最多可能出现的次数为 1 0 10 10^{10} 1010会爆long，所以要用大数类大数类的运算方法不会直接修改大数的值，需要重新赋值调试技巧：当二分出现错误的时候从两个方向考虑，排序和二分

import java.util.*;import java.io.*;import java.math.*;class Main { BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));String sp[];int[] a = new int[100010], b = new int[100010], c = new int[100010];int n;void run() throws Exception { sp = reader.readLine().split(" ");n = Integer.parInt(sp[0]);sp = reader.readLine().split(" ");for (int i = 0; i < n; i++) { a[i] = Integer.parInt(sp[i]);}sp = reader.readLine().split语文的核心素养(" ");for (int i = 0; i < n; i++) { b[i] = Integer.parInt(sp[i]);}sp = reader.readLine().split(" ");for (int i = 0; i < n; i++) { c[i] = Integer.parInt(sp[i]);}// 对a数组和c数组先排序Arrays.sort(a, 0, n);Arrays.sort(c, 0, n);BigInteger cnt = new BigInteger("0");// 遍历b数组for (int i =我仰望星空 0; i < n; i++) { BigInteger cnt_a = new BigInteger("0"); BigInteger cnt_c = new BigInteger("0");;// 从a数组中找到所有小于b[i]的数// 其最大值比b[i]还小那么cnt_a = n// 其最小值不小于b[i]那么cnt_a = 0// 有一部分小于b[i]，一部分大于b[i]，则用二分找到第一个大于b[i]的数的下标if (a[n - 1] < b[i]) cnt_a = new BigInteger(String.valueOf(n));el if (a[0] >= b[i]) cnt_a = new BigInteger(String.valueOf(0));el cnt_a = new BigInteger(String.valueOf(archFirstBigOrEqualNum(b[i])));// 从c数组中找到所有大于b[i]的数// 其最小值比b[i]还那么cnt_c = n// 其最大值不大于b[i]那么cnt_c = 0if (c[0] > b[i]) cnt_c = new BigInteger(String.valueOf(n));el if (c[n - 1] <= b[i]) cnt_c = new BigInteger(String.valueOf(0));el cnt_c = new BigInteger(String.valueOf(n - archFirstBigNum(b[i]))); cnt = cnt.add(cnt_a.multiply(cnt_c));}System.out.println(cnt);}int archFirstBigOrEqualNum(int target) { int l = 0, r = n - 1;while (l < r) { int mid = (l + r) / 2;if (a[mid] < target) { l = mid + 1;} el { r = mid;}}return l;}int archFirstBigNum(int target) { int l = 0, r = n - 1;while (l < r) { int mid = (l + r) / 2;if (c[mid] <= target) { l = mid + 1;} el { r = mid;}}return l;}public static void main(String[] args) throws Exception { new Main().run();}}