2018 蓝桥杯 递增三元组 sort排序

发表于 分类于 阅读次数： 本文字数： 414 阅读时长 ≈ 2 分钟

这是2018年蓝桥杯C语言省赛B组的第六题

题目：
给定三个整数数组
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。
1 <= N <= 100000 0 <= Ai, Bi, Ci <= 100000

输出
一个整数表示答案

样例输入
3
1 1 1
2 2 2
3 3 3

样例输出
27

OJ链接

思路：先用sort对三个数组进行排序。随后对B数组进行遍历，用lower_bound函数求出A数组中小于B数组当前元素的数量，用upper_bound函数求出C数组中大于B数组当前元素的数量，两者相乘算出B数组当前元素下可行解的数量，把B数组遍历一遍即可求出总解。
PS：记得用long long，用int的话会爆。

AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<bits/stdc++.h>
using namespace std;

int a[100001],b[100001],c[100001];

int main()
{
	int n;
	scanf("%d",&n);
	for(int now=0;now<n;now++)
	{
		scanf("%d",&a[now]);
	}
	for(int now=0;now<n;now++)
	{
		scanf("%d",&b[now]);
	}
	for(int now=0;now<n;now++)
	{
		scanf("%d",&c[now]);
	}
	
	sort(a,a+n);//排序
	sort(b,b+n);
	sort(c,c+n);
	
	long long ans=0;//记得用long long
	
	for(int now=0;now<n;now++)//b为中间值 遍历
	{
		long long s1=lower_bound(a,a+n,b[now])-a;//获取a中小于b【now】的个数
		long long s2=n-(upper_bound(c,c+n,b[now])-c);//获取c中大于b【now】的个数
		ans+=s1*s2;
	}
	
	cout<<ans;
	
	return 0;
	
}