每日算法打卡：递增三元组

算法
818 words

原题链接

1236. 递增三元组

题目难度：中等

题目来源：第九届蓝桥杯省赛C++ B组,第九届蓝桥杯省赛Java B组

题目描述

给定三个整数数组

$A = [A_1, A_2, … A_N]$,
$B = [B_1, B_2, … B_N]$,
$C = [C_1, C_2, … C_N]$,

请你统计有多少个三元组 $(i, j, k)$ 满足：

  1. $1 \le i, j, k \le N$
  2. $A_i < B_j < C_k$

输入格式

第一行包含一个整数 $N$。

第二行包含 $N$ 个整数 $A_1, A_2, … A_N$。

第三行包含 $N$ 个整数 $B_1, B_2, … B_N$。

第四行包含 $N$ 个整数 $C_1, C_2, … C_N$。

输出格式

一个整数表示答案。

数据范围

$1 \le N \le 10^5$,
$0 \le A_i,B_i,C_i \le 10^5$

输入样例：

1
2
3
4
3
1 1 1
2 2 2
3 3 3

输出样例：

1
27

题目分析

这道题的意思很清楚，就是从A、B、C三个数组中选出三个数满足严格小于关系，问满足条件的三元组的个数

对于枚举类型的题目，最重要的就是枚举的顺序，要注意不重不漏，其次就是要对代码进行优化，利用题目性质，等式，进行优化

如果我们从暴力来做就是用三重循环，直接判断计数

这里考虑到这个不等式的关系，就是A小于B小于C，如果我们枚举的是A或者C，那么对于我们统计的B和C的数量，是无法简单的使用乘法原理直接相乘的，因为乘法原理是要求独立的，因此我们在这里是需要枚举B的，对于每一个B只需要在计算满足要求的A的个数，满足要求的C的个数，再相乘即可

那么这里的问题就是，如何快速计算出满足要求的A和C的个数，这其实是同一个问题了

我们将其抽象出来就是，在A中有多少个数小于B

我们能想到的第一个方法就是使用前缀和，第二个方法就是排序+二分，第三种方法就是使用双指针算法，我们暂时就先只使用前两个方法来做

我们首先开一个count数组，表示在A数组中，i的值出现的次数

然后我们再对这个count数组做前缀和，他的含义就是在A中从0到i的数字出现了多少次

示例代码

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
#include<iostream>
#include<cstring>
using namespace std;
using ll = long long;

const int N = 100010;


int n;
int a[N], b[N], c[N];
int ap[N], cp[N]; // a和c的前缀
int cnt[N], s[N];

int main()
{
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i], a[i]++;
    for (int i = 0; i < n; i++) cin >> b[i], b[i]++;
    for (int i = 0; i < n; i++) cin >> c[i], c[i]++;

    // 计数+前缀和
    for (int i = 0; i < n; i++) cnt[a[i]]++;
    for (int i = 1; i < N; i++) s[i] = s[i - 1] + cnt[i];
    for (int i = 0; i < n; i++) ap[i] = s[b[i] - 1];

    memset(cnt, 0, sizeof(cnt));
    memset(s, 0, sizeof(s));

    for (int i = 0; i < n; i++) cnt[c[i]]++;
    for (int i = 1; i < N; i++) s[i] = s[i - 1] + cnt[i];
    for (int i = 0; i < n; i++) cp[i] = s[N - 1] - s[b[i]];

    ll ans = 0;
    for (int i = 0; i < n; i++) ans += (ll)ap[i] * cp[i];
    cout << ans << '\n';
    return 0;
}
Comments