第九屆藍橋杯Java B——遞增三元組
給定三個整數陣列
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 <= 1000000 <= Ai, Bi, Ci <= 100000
【輸出格式】
一個整數表示答案
【輸入樣例】
3
1 1 1
2 2 2
3 3 3
【輸出樣例】
27
資源約定:
峰值記憶體消耗(含虛擬機器) < 256M
CPU消耗< 1000ms
把a陣列升序排序,c陣列降序排序,然後遍歷b陣列,找a陣列有多少個比b陣列小,再找c陣列有多少個比b陣列大
import java.io.BufferedInputStream; import java.util.Arrays; import java.util.Collections; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner cin = new Scanner(new BufferedInputStream(System.in)); int n = cin.nextInt(); int[] a = new int[n]; int[] b = new int[n]; Integer[] c = new Integer[n]; long ans = 0L; for (int i = 0; i < n; i++) a[i] = cin.nextInt(); for (int i = 0; i < n; i++) b[i] = cin.nextInt(); for (int i = 0; i < n; i++) c[i] = cin.nextInt(); Arrays.sort(a); Arrays.sort(c, Collections.reverseOrder()); int[] resa = new int[n]; int[] resc = new int[n]; for (int i = 0; i < n; i++) { // traverse B for (int j = 0; j < n; j++) // traverse A if (a[j] < b[i]) resa[i]++; else break; for (int j = 0; j < n; j++) // traverse C if (c[j] > b[i]) resc[i]++; else break; } for (int i = 0; i < n; i++) ans += resa[i] * resc[i]; System.out.println(ans); } }