本文共 1074 字，大约阅读时间需要 3 分钟。

第九届蓝桥杯Java试题–递增三元组

题目：

给定三个整数数组

A = [A1, A2, … AN], B = [B1, B2, … BN], C = [C1, C2, … CN]， 请你统计有多少个三元组(i, j, k) 满足：

1. 1 <= i, j, k <= N
2. 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

分析：这道题我首先想到的是暴力计算，通过嵌套三个循环将所有组合全部循环出，对每个组合判断，最终得出结果，但如果给出的N很大，如果N=1000000，则次循环需要循环100000* 100000* 100000次，显然这种方法不是很合适。

如果将后三行中的第二行作为参考，建立两个数组min[ ] 和max[ ] ，将中间一行元素进行遍历，min数组用来保存上一行中比中间行元素小的个数，例如：上两行为： 2 6 3 3 7 5 那么min[0] = 1，因为第一行只有2比3小，则min[1] = 3，min[2] = 2。 同理再中间这行和最后一行元素，用max保存最后一行比中间行大的元素的个数。

最后将min数组和max数组对应元素相乘，并将结果相加，得出最终结果。

代码：

import java.util.Scanner;public class Demo1 {	public static void main(String[] args) {		Scanner in=new Scanner(System.in);		int sum=0;		int n=in.nextInt();		int [][] a=new int[3][n];		int min[]=new int[n];		int max[]=new int[n];		for(int i=0;i<3;i++)			for(int j=0;j

这应该不是最简便的方法，但比起第一种还是有所进步的，应该会比第一种好些。

转载地址：http://wzwai.baihongyu.com/