AcWing 1236. 递增三元组 (Java 二分 Or 前缀和)
原题链接
中等
作者:
Limited
,
2021-02-01 22:50:22
,
所有人可见
,
阅读 258
二分
import java.lang.*;
import java.util.*;
public class Main {
static Scanner scanner = new Scanner(System.in);
static int n;
static int[] a = new int[100010], b = new int[100010], c = new int[100010];
public static void main(String[] args) {
n = scanner.nextInt();
for (int i = 0; i < n; i++) {
a[i] = scanner.nextInt();
}
for (int i = 0; i < n; i++) {
b[i] = scanner.nextInt();
}
for (int i = 0; i < n; i++) {
c[i] = scanner.nextInt();
}
// 升序
Arrays.sort(a, 0, n);
Arrays.sort(b, 0, n);
Arrays.sort(c, 0, n);
// 注意 long 最终结果数据量很大
long cnt = 0;
// a < b < c 遍历数组b只需要一次循环
for (int i = 0; i < n; i++) {
long nums0 = 0, nums1 = 0;
// 二分找到 最后一个 小于b[i] 的a[xx]位置
int l = 0, r = n - 1;
while (l < r) {
int mid = l + r + 1 >> 1;
if (a[mid] < b[i]) {
l = mid;
} else {
r = mid - 1;
}
}
// 注意判断是否能找到 如果找不到 下一个b[i]更大 还有可能情况 所以continue
if (a[l] >= b[i]) {
continue;
}
// 找得到就计算个数 取左段区间总个数 所以 l+1
nums0 = l + 1;
// 重置左右界 二分查找 第一个 大于b[i] 的c[xx]位置
l = 0;
r = n - 1;
while (l < r) {
int mid = l + r >> 1;
if (b[i] < c[mid]) {
r = mid;
} else {
l = mid + 1;
}
}
// 判断是否找到 若未找到 下一个b[i]更大 c[]中更不可能有匹配项 break退出循环
if (b[i] >= c[l]) {
break;
}
// 若找到 取右段区间总个数 所以 n-l
nums1 = n - l;
// a有nums0种 c有nums1种 总共 nums0*nums1 种组合方式
cnt += nums0 * nums1;
}
System.out.println(cnt);
}
}
前缀和
import java.lang.*;
import java.util.*;
public class Main {
static Scanner scanner = new Scanner(System.in);
static int n;
static int[] b = new int[100010], sumA = new int[100010], sumC = new int[100010],
countA = new int[100010], countC = new int[100010];
public static void main(String[] args) {
n = scanner.nextInt();
// 数组a、c 在读入时只存 该数字出现的次数
for (int i = 0; i < n; i++) {
countA[scanner.nextInt()]++;
}
for (int i = 0; i < n; i++) {
b[i] = scanner.nextInt();
}
for (int i = 0; i < n; i++) {
countC[scanner.nextInt()]++;
}
// 计算前缀和 sumX[i]表示数组X的数字[0, i]出现次数总和
sumA[0] = countA[0];
sumC[0] = countC[0];
for (int i = 1; i < 100010; i++) {
sumA[i] = sumA[i - 1] + countA[i];
sumC[i] = sumC[i - 1] + countC[i];
}
// 遍历数组B 三元组总数 = a[]中小于b[i]的所有数字出现次数 * c[]中大于b[i]的所有数字出现次数
long cnt = 0;
for (int i = 0; i < n; i++) {
// 所给数范围 [0, 1e5] 当b[i]取最大或最小值时 必不满足a<b<c
if (b[i] == 0 || b[i] == 100000) {
continue;
}
// 从前缀和的定义出发
cnt += (long) sumA[b[i] - 1] * (sumC[100000] - sumC[b[i]]);
}
System.out.println(cnt);
}
}