题目
给定三个整数数组
,
,
,
请你统计有多少个三元组 满足:
输入格式
第一行包含一个整数 。
第二行包含 个整数 。
第三行包含 个整数 。
第四行包含 个整数 。
输出格式
一个整数表示答案。
数据范围
,
输入样例:
3
1 1 1
2 2 2
3 3 3
输出样例:
27
解题
方法一:排序 二分查找
思路
输入三个数组并排序。
在第二个数组中枚举中间数字 :
- 在第一个数组中二分查找严格小于 的最后一个数的下标 。
- 在第三个数组中二分查找严格大于 的第一个数的下标 。
根据乘法原理,以 为中间数字的三元组共有 个,那么把所有的三元组累加起来就是答案。
代码
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);
}
}
评论区