P8667 [蓝桥杯 2018 省 B] 递增三元组题解

liruixiong0101 · 2023-04-26 14:11:11 · 题解

P-1 前言：

双倍经验：[ABC077C] Snuke Festival。

P0 前置知识：

二分。

P1 题意：

给定三个长度为 n 的整数数组 a,b,c。
请你统计有多少个三元组 (i,j,k) 满足：

1\le i,j,k\le n
a_i < b_j < c_k

P3 思路：

首先想到的就是暴力，三层循环枚举。
时间复杂度：O(n^3)，分数：60pts，不可过。
暴力应该人人都会写，就不提供代码了。

暴力过不了就想优化。
我们枚举了前两层循环 i,j，若 a_i<b_j 那么就不必再枚举所有的 k 只需要所有大于 b_j 的 k 的取值种数，加上即可。这可以用二分解决。
时间复杂度：O(n^2\log n)，分数：72pts，不可过。
代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 5;
int n , a[N] , b[N] , c[N] , ans;
signed main(){
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= n; i++) cin >> b[i];
    for(int i = 1; i <= n; i++) cin >> c[i];
    sort(a + 1 , a + 1 + n);
    sort(b + 1 , b + 1 + n);
    sort(c + 1 , c + 1 + n);
    //排序，好进行二分
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            if(a[i] >= b[j]) continue;
            //二分的前提是a[i] < b[j]
            int num = upper_bound(c + 1 , c + 1 + n , b[j]) - c;
            ans += n - num + 1;
            //二分找出所有大于b[j]的c[k]，ans累加
        }
    }
    cout << ans;
    return 0;
}

既然你都可以用二分来找出满足条件的 k，那我为什么不可以换一种枚举方式把满足条件的 i 或 j 也给找出来呢。
仔细看条件二：a_i<b_j<c_k。
有没有发现这个 b_j 很特殊，他在这个不等式的中间。
我们现在把这个不等式变一下。

a_i<b_j<c_k

\begin{cases} a_i<b_j\\ c_k>b_j\\ \end{cases}

（下面的两个不等式为且的关系）
你发现了吗？
我们可以枚举 j 再通过二分找出满足条件的 i,k 的种类数分别记为 cnta,cntb。根据乘法原理，在每次循环将 cnta\times cntb 累计到 ans 里即可。
时间复杂度：O(n\log n)，分数：100pts，可过。

P4 代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 5;
int n , a[N] , b[N] , c[N] , ans;
signed main(){
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= n; i++) cin >> b[i];
    for(int i = 1; i <= n; i++) cin >> c[i];
    sort(a + 1 , a + 1 + n);
    sort(c + 1 , c + 1 + n);
    //排序，好进行二分
    for(int j = 1; j <= n; j++){
        int cnta = lower_bound(a + 1 , a + 1 + n , b[j]) - a - 1;
        int cntc = upper_bound(c + 1 , c + 1 + n , b[j]) - c;
        cntc = n - cntc + 1;
        //二分找出i的种类数和j的种类数
        ans += cnta * cntc;//乘法原理累计答案
    }
    cout << ans;
    return 0;
}

记得开 long long！！！

P8667 [蓝桥杯 2018 省 B] 递增三元组 题解