2018年第九届蓝桥杯省赛-F.递增三元组

2022-03-22 · 51次阅读 · 原创 · 数据结构与算法

#蓝桥杯 #题解 #前缀和

原题链接

题面

给定三个整数数组

$A = [A_1, A_2, \cdots A_N]$ ,

$B = [B_1, B_2, \cdots B_N]$ ,

$C = [C_1, C_2, \cdots C_N]$ ，

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

$1 \leq i, j, k \leq N$ ;
$A_i < B_j < C_k$ 。

输入描述

第一行包含一个整数 N。

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

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

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

其中， $1 \leq N \leq 10^5, 0 \leq Ai, Bi, Ci \leq 10^5$ 。

输出描述

输出一个整数表示答案。

输入样例

输出样例

题解

前缀和

本题题意为为对于数组 B 中的一个元素，在 A 数组中找到一个比其小，在C数组中找到一个比其大的三元组，统计存在多少个这样的三元组。则可以转换为 B 中的一个元素，A中比他小的数的个数乘上 B中比他大的个数，则为B中该元素组成的三元组的个数，再对B中每个元素前述计算求和即为结果。

由于三个数组的元素值在 $[0, 10^5]$ 之间，可以分别统计数组 A 和 B 中每个数的出现次数，并计算前缀和 SA 和 SB，这样就可以知道数组 A 中小于 x 的值的元素个数为 SA[x - 1]，而数组 B 中大于 x 的值的元素个数为 SB[最大数] - SB[x]。

注意，由于数组元素值为从 0 开始，而前缀和统计的是从下标 1 开始的，所以需要将原来的数组元素值都加一，让其从下标 1 开始，具体见代码。

代码

#include<bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;
int n, b[N], sa[N], sc[N];

int main() {
    cin >> n;
    //读取 a 并统计每个数出现的次数
    for (int i = 1, x; i <= n; i++) {
        scanf("%d", &x);
        sa[x + 1]++;
    }
    //读取 b
    for (int i = 1; i <= n; i++) scanf("%d", &b[i]);
    //读取 c 并统计每个数出现的次数
    for (int i = 1, x; i <= n; i++) {
        scanf("%d", &x);
        sc[x + 1]++;
    }

    //计算 a 和 b 数字出现次数的前缀和
    for (int i = 1; i <= 100001; i++) {
        sa[i] += sa[i - 1];
        sc[i] += sc[i - 1];
    }

    long long s = 0;
    for (int i = 1; i <= n; i++) {
        int x = b[i] + 1;
        s += sa[x - 1] * 1ll * (sc[100001] - sc[x]);
    }
    cout << s << endl;

    return 0;
}

标题：	2018年第九届蓝桥杯省赛-F.递增三元组
链接：	https://www.fightingok.cn/detail/206
更新：	2022-09-18 22:48:07
版权：	本文采用 CC BY-NC-SA 3.0 CN 协议进行许可