本文主要是介绍【蓝桥杯】递增三元组 (二分, lower_bound, upper_bound)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
有三个数组A，B，C，每个数组中有n个数，你可以从每个数组中找一个数，使得Ai<Bj<Ck ,(1<=I,j,k<=n)(1<=n<=100000,1<=Ai,Bj,Ck<=1000000)，求最多可以组出多少三元组
Input
有多组输入
第一行输入n
接下来三行输入A，B，C三个数组，每个数组n个数
Output
每行一个整数，表示最多有多少三元组
Sample Input
3
1 1 1
2 2 2
3 3 3
3
1 2 3
1 2 3
1 2 3
Sample Output
27
1
思路分析：
看n的数据，时间复杂度只能在O(n)或者O(ngln)了。
其实仔细分析可以想到排序之后，可以用到二分查找。那么怎么设计呢？
一开始我是想的遍历a，这样b数组就得找第一个比a[i]大的数b[j]，c数组找第一个比b[j]大的数c[k]. 但是在草稿纸模拟一下发现根本不可行，b数组如果不遍历会把一些重复的元素算进去。因此我选择遍历b数组。
于是，在a数组找比b[j]小的索引i，在c数组找比b[j]大的索引k. 这样可以用lower_bound和upper_bound找出来，然后根据排列组合的乘法原理求出答案。
这里顺带介绍一下lower_bound和upper_bound用法。
lower_bound(a,a+n,k)表示在a数组[0,n)里找第一个大于等于k的值的迭代器。
upper_bound(a,a+n,k)表示b数组[0,n)里找第一个大于k的值的迭代器。
lower_bound(a,a+n,k)-a表示第一个大于等于k的值的索引。
distance(a,b)表示迭代器a和b之间的元素个数( [a,b) ). (注意a的位置要小于b，不然会报错).
distance的用处在于集合set里，set是一个平衡树，并不是连续的内存空间，想获取元素个数只能用distance.
#include <bits/stdc++.h>
using namespace std;int main()
{int a[] = {1,2,2,3,3,5}, index_a, n = 6;index_a = lower_bound(a,a+n,2)-a; //索引 1 cout<<index_a<<endl;index_a = distance(a, lower_bound(a,a+n,2)); //索引 1 cout<<index_a<<endl;index_a = upper_bound(a,a+n,2)-a; //索引 3 cout<<index_a<<endl;index_a = distance(a, upper_bound(a,a+n,2)); //索引 3 cout<<index_a<<endl;index_a = lower_bound(a,a+n,5)-a; //索引 5cout<<index_a<<endl;index_a = upper_bound(a,a+n,5)-a; //超出范围，索引 6 cout<<index_a<<endl;
}
介绍完lower_bound和upper_bound后，来分析一波。
我们遍历b数组，在a数组找比b[j]小的个数，在c数组找比b[j]大的个数.
第一个直接lower_bound(a.begin(), a.end(), b[i]) - a.begin();
lower_bound在a数组找到第一个比b[j]大于等于的数的索引，那么个数就是这个索引-a.begin().因为个数是在左闭右开的区间里，因为右开，所以区间里所有的数都比b[j]小。
第二个直接index_b = upper_bound(c.begin(), c.end(), b[i])- c.begin()求出第一个大于b[j]的数的索引，n-index_b就是索引区间[b,n)的个数。
最后，根据乘法原理，两个个数相乘。不过这两个值都可能在105，相乘会爆int范围，这个要注意！！！不然就WA掉了，而且很难察觉！
另外，这道题不需要去重，不可思议。
下面上代码。
#include <iostream>
#include <vector>
#include <algorithm>
#define ll long long
#define MAX 100010
using namespace std;int main()
{ll ans;int n, x;while(cin>>n){ans = 0;vector<int> a, b, c;for(int i = 0;i < n;i++)scanf("%d",&x), a.push_back(x);for(int i = 0;i < n;i++)scanf("%d",&x), b.push_back(x);for(int i = 0;i < n;i++)scanf("%d",&x), c.push_back(x);sort(a.begin(), a.end());sort(b.begin(), b.end());sort(c.begin(), c.end());for(int i = 0;i < n;i++){
// if(b[i] == b[i-1]) continue; 不需要去重 ll index_a = lower_bound(a.begin(), a.end(), b[i]) - a.begin(); //索引a ll index_c = upper_bound(c.begin(), c.end(), b[i])- c.begin(); //索引c
// cout<<index_a<<" "<<index_c<<endl;ans += index_a * (n-index_c);}cout<<ans<<endl;}return 0;
}
这篇关于【蓝桥杯】递增三元组 (二分, lower_bound, upper_bound)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
