2018年蓝桥杯C/C++ B组省赛试题F：递增三元组题解

快来打我* 2022-12-28 14:18 100阅读 0赞

### 文章目录 ###

*  题目描述
 *   *  输入
     *  输出
     *  样例输入
     *  样例输出
 *  算法思路
 *  解题代码
 *   *  1.二重循环 O(n \* n \* logn)）
     *  2.一重循环 O(n \* logn)
 *  错题总结
 *   *  \*\*upper\_bound和lower\_bound的用法\*\*
     *   *  1、在从小到大的排序数组中，
         *  2、在从大到小的排序数组中

--------------------

# 题目描述 #

给定三个整数数组  
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

## 样例输出 ##

# 算法思路 #

两重循环，找出符合条件的`ai`和`bj`的位置，随后用`upper_bound()`去寻找第一个大于`bj`的`ck`的位置

# 解题代码 #

## 1.二重循环 O(n \* n \* logn)） ##

//
    //  main.cpp
    //  2018lanqiao-f
    //
    //  Created by 陈洋 on 2020/10/11.
    //  Copyright © 2020 陈洋. All rights reserved.
    //
    
    #include <iostream>
    #include <vector>
    using namespace std;
    
    vector<int> a;
    vector<int> b;
    vector<int> c;
    int n,t;
    
    int main(int argc, const char * argv[]) {
        
        cin >> n;
    
        for(int i = 0; i < n; i++){
        
            cin >> t;
            a.push_back(t);
        }
        
        for(int i = 0; i < n; i++){
        
            cin >> t;
            b.push_back(t);
        }
        
        for(int i = 0; i < n; i++){
        
            cin >> t;
            c.push_back(t);
        }
        
        sort(a.begin(), a.end());
        sort(b.begin(), b.end());
        sort(c.begin(), c.end());
    
        long long ans = 0;
        for(int i = 0; i < n; i++){
        
            for(int j = 0; j < n; j++){
        
                if(a[i] < b[i]){
        
                    int k = upper_bound(c.begin(), c.end(), b[i]) - c.begin();
                    ans += n - k;
                }
            }
        }
        
        cout << ans << endl;
    }

## 2.一重循环 O(n \* logn) ##

其实有更快的解题思路

*  只需要一重循环判断`bj`的位置
 *  从`ai`中找到第一个大于等于`bj`的数字，即用`lower_bound(a.begin(), a.end(), bj) - a.begin()`，然后向前退后一个下标就是 **小于`bj`的最大的`ai`**
 *  从`ck`中找到第一个大于`bj`的数字，即用`upper_bound(c.begin(), c.end(), bj) - c.begin()`
 *  因此就可以以**时间复杂度为O(n \* logn)解题**

--------------------

# 错题总结 #

## **upper\_bound和lower\_bound的用法** ##

### 1、在从小到大的排序数组中， ###

`lower_bound( begin,end,num)`：从数组的`begin`位置到`end-1`位置二分查找**第一个大于或等于**`num`的数字，**找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。**

`upper_bound( begin,end,num)`：从数组的`begin`位置到`end-1`位置二分查找**第一个大于**`num`的数字，**找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。**

### 2、在从大到小的排序数组中 ###

重载lower\_bound()和upper\_bound()

`lower_bound( begin,end,num,greater\<type>() )`：从数组的`begin`位置到`end-1`位置二分查找**第一个小于或等于**`num`的数字，**找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。**

`upper_bound( begin,end,num,greater\<type>() )`：从数组的`begin`位置到`end-1`位置二分查找**第一个小于**`num`的数字，**找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。**

参考：[关于lower\_bound( )和upper\_bound( )的常见用法][lower_bound_ _upper_bound_]

[lower_bound_ _upper_bound_]: https://blog.csdn.net/qq_40160605/article/details/80150252