给定三个整数数组
- A = [A1, A2, ... AN],
- B = [B1, B2, ... BN],
- C = [C1, C2, ... CN],
请你统计有多少个三元组 (i, j, k) 满足:
- 1 <= i, j, k <= N
- Ai <Bj < Ck
[输入格式]
第一行包含一个整数 N.
第二行包含 N 个整数 A1, A2, ... AN.
第三行包含 N 个整数 B1, B2, ... BN.
第四行包含 N 个整数 C1, C2, ... CN.
对于 30% 的数据, 1 <= N <= 100
对于 60% 的数据, 1 <= N <= 1000
对于 100% 的数据, 1 <= N <= 100000 0 <= Ai, Bi, Ci <= 100000
[输出格式]
一个整数表示答案
[输入样例]
- 3
- 1 1 1
- 2 2 2
- 3 3 3
[输出样例]
27
资源约定:
峰值内存消耗 (含虚拟机) < 256M
CPU 消耗 < 1000ms
该题主要考查枚举及对枚举的优化, 一点空间换时间的思维
枚举: 三重循环枚举 O(n^3), 枚举优化, 先将给定三个数组排序, 枚举并记录 a 数组中每个数, b 数组大于该数的个数情况, 同样在枚举 b 中每个数, c 数组中大于该数的情况, 对应乘积在求和即为所求 (理解该处 -- 原给定数组已排好序)O(n^2)
自己的理解: 对于类似枚举的算法题来说, 最简单的直接暴力枚举是首先想到的, 也是思路最简单清晰的, 当然不论是从题目实际考虑, 还是对枚举的经验来说直接暴力枚举一定是可以优化的, 我的优化思路就是朝着时间复杂度的方向优化, O(n^3) 就会考虑怎样优化到 O(n^2) 或 O(n^2lgn),O(n^2) 就考虑如何优化到 O(nlgn), 当然巧用排序和二分查找也是顺带的想法. 希望对你有些帮助
java 代码参考:
- import java.util.Arrays;
- import java.util.Scanner;
- public class Main {
- public static void main(String[] args) {
- Scanner sc = new Scanner(System.in);
- int n = sc.nextInt();
- int[] a = new int[n];
- int[] b = new int[n];
- int[] c = new int[n];
- for (int i = 0; i < a.length; i++) {
- a[i] = sc.nextInt();
- }
- for (int i = 0; i < a.length; i++) {
- b[i] = sc.nextInt();
- }
- for (int i = 0; i < a.length; i++) {
- c[i] = sc.nextInt();
- }
- int res = solve2(a, b, c, n);
- System.out.println(res);
- }
- /**
- * 将三个数组排序 (O(nlgn))
- * 统计 a 数组中每个数在 b 中比该数大的个数
- * 在枚举 b 中每个数 c 中更大的个数, 乘积和即为所求
- * O(n^2)
- * @param a
- * @param b
- * @param c
- * @param n
- * @return
- */
- private static int solve2(int[] a, int[] b, int[] c, int n) {
- int[] b_amax = new int[n];
- int ans = 0;
- Arrays.sort(a);Arrays.sort(b);Arrays.sort(c);
- for(int i = 0; i < n; i++) {
- for(int j = 0; j < n; j++) {
- if(b[j]> a[i]) {
- b_amax[i] = n - j;
- break;
- }
- }
- }
- // 枚举 b, 计算结果
- for(int i = 0; i <n; i++) {
- for(int j = 0; j < n; j++) {
- if(c[j]> b[i]) {
- ans += (n - j)*b_amax[i];
- break;
- }
- }
- }
- return ans;
- }
- // 暴力求解 O(n^3)
- private static int solve(int[] a, int[] b, int[] c, int n) {
- int ans = 0;
- for(int i = 0; i < n; i++) {
- for(int j = 0; j < n; j++) {
- for(int k = 0; k < n; k++) {
- if(a[i] < b[j]&&b[j] < c[k])
- ans++;
- }
- }
- }
- return ans;
- }
- }
来源: http://www.jianshu.com/p/dbbc9d3d4f1d