star

**方法二o(nlogn)**:将a，c数组升序排列，之后a，c具有单调性，遍历b数组，在a中查找小于bj的最后一个元素下标k，之后有k+1个元素小于bj，同理在c中二分查找第一个大于bi的元素下标t,于是就有n-t个元素大于bj，(k+1)*(n-t)就是bj这个元素所有满足 Ai < Bj < Ck的个数了，把所有bj的这个个数加起来既是结果,但是这个二分不是常规二分，不太好写，一般都需要debug几次，不太建议

**方法三o(n)** :前缀和，依次统计a，c数组中每个数字出现的次数，之后算出a，c数组的前缀和数组sac，scc，
sac[b[i] - 1]既a数组中小于b[i]的数目
scc[N - 1 ]-scc[b[i]]既c数组中大于b[i]的数目
两个数目相乘既就是b[i]这个元素所有满足 Ai < Bj < Ck的个数了，把所有b[i]的这个个数加起来既是结果

### 暴力破解参考代码

```java
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	static BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer stringTokenizer = new StringTokenizer("");

static String nextLine() throws IOException {
		return bufferedReader.readLine();
	}

static String next() throws IOException {
		while (!stringTokenizer.hasMoreTokens()) {
			stringTokenizer = new StringTokenizer(bufferedReader.readLine());
		}
		return stringTokenizer.nextToken();
	}

static int nextInt() throws NumberFormatException, IOException {
		return Integer.parseInt(next());
	}

public static void main(String[] args) throws NumberFormatException, IOException {
		int n = nextInt();
		int a[] = new int[n];
		int b[] = new int[n];
		int c[] = new int[n];
		for (int i = 0; i < n; i++) {
			a[i] = nextInt();
		}
		for (int i = 0; i < n; i++) {
			b[i] = nextInt();
		}
		for (int i = 0; i < n; i++) {
			c[i] = nextInt();
		}
		int num = 0;
		for (int k = 0; k < n; k++) {
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					if (a[k] < b[i] && b[i] < c[j]) {
						num++;
					}
				}
			}
		}
		System.out.println(num);
	}
}
```

### 前缀和参考代码

```java
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	static BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer stringTokenizer = new StringTokenizer("");

static String nextLine() throws IOException {
		return bufferedReader.readLine();
	}

static int nextInt() throws NumberFormatException, IOException {
		return Integer.parseInt(next());
	}

// 前缀和解三元组
	// 不知道各数组中每个元素的范围，所以需要尽可能大，但不能超过要求的空间，也不能因此而让时间超，前缀和写下来时间复杂度估计O（N），折中取10的六次方
	final static int N = 100000;

public static void main(String[] args) throws NumberFormatException, IOException {
		int n = nextInt();
		int[] ac = new int[N];
		int[] sac = new int[N];
		int[] scc = new int[N];
		int[] cc = new int[N];
		int[] b = new int[n];
		// 统计a数组每个数字出现的次数
		for (int i = 0; i < n; i++) {
			int t = nextInt();
			// 为避免后面求前缀和算掉0，整体偏移一位
			ac[t + 1]++;
		}
		for (int i = 1; i < N; i++) {
			sac[i] = sac[i - 1] + ac[i];
		}
		// 填充b数组
		for (int i = 0; i < n; i++) {
			b[i] = nextInt() + 1;
		}
		// 统计c数组每个数字出现的次数
		for (int i = 0; i < n; i++) {
			int t = nextInt();
			cc[t + 1]++;
		}
		for (int i = 1; i < N; i++) {
			scc[i] = scc[i - 1] + cc[i];
		}
		int num = 0;
		for (int i = 0; i < n; i++) {
			int anum = sac[b[i] - 1];
			int cnum = scc[N - 1 ]-scc[b[i]];
			num += anum * cnum;
		}
		System.out.println(num);
	}
}
```

0.0分

1 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

star

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题9.1 （C语言代码）

C语言程序设计教程（第三版）课后习题8.7 （C++代码）

2004年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

【绝对值排序】（C++代码）（利用两个库函数——abs()求绝对值和 sort()快排）

K-进制数（C++代码）

递增三元组（逐层优化）

评论区

精彩推荐

汽水瓶（C语言代码）

C语言训练-求函数值（C语言代码）

【回文数(二)】（C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题6.10 （C语言代码）

2006年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言程序设计教程（第三版）课后习题6.2 （C语言代码）

C语言程序设计教程（第三版）课后习题6.3 （C语言代码）

C语言程序设计教程（第三版）课后习题8.8 （C语言代码）

简单的a+b （C语言代码）

star

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题9.1 （C语言代码）

C语言程序设计教程（第三版）课后习题8.7 （C++代码）

2004年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

【绝对值排序】 （C++代码）（利用两个库函数——abs()求绝对值 和 sort()快排）

K-进制数 （C++代码）

递增三元组（逐层优化）

评论区

精彩推荐

汽水瓶 （C语言代码）

C语言训练-求函数值 （C语言代码）

【回文数(二)】 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题6.10 （C语言代码）

2006年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言程序设计教程（第三版）课后习题6.2 （C语言代码）

C语言程序设计教程（第三版）课后习题6.3 （C语言代码）

C语言程序设计教程（第三版）课后习题8.8 （C语言代码）

简单的a+b （C语言代码）

【绝对值排序】（C++代码）（利用两个库函数——abs()求绝对值和 sort()快排）

K-进制数（C++代码）

　　评论区

汽水瓶（C语言代码）

C语言训练-求函数值（C语言代码）

【回文数(二)】（C语言代码）