第九届蓝桥杯省赛C++B组递增三元组【二分】题解

心已赠人 2021-07-24 20:29 370阅读 0赞

### 目录 ###

*   *   *  1.题目
         *  2.思路
         *  3.代码

### 1.题目 ###

给定三个整数数组  
A=\[A1,A2,…AN\],  
B=\[B1,B2,…BN\],  
C=\[C1,C2,…CN\],  
请你统计有多少个三元组 (i,j,k) 满足：  
1≤i,j,k≤N  
Ai<Bj<Ck  
**输入格式**  
第一行包含一个整数 N。  
第二行包含 N 个整数 A1,A2,…AN。  
第三行包含 N 个整数 B1,B2,…BN。  
第四行包含 N 个整数 C1,C2,…CN。  
**输出格式**  
一个整数表示答案。  
**数据范围**  
1≤N≤105,  
0≤Ai,Bi,Ci≤105  
**输入样例：**  
3  
1 1 1  
2 2 2  
3 3 3  
**输出样例：**

### 2.思路 ###

**二分**  
**1**.先对三个数组进行sort排序。  
**2**.然后遍历b数组,对于b中的每一个数b\[i\],在a数组中寻找最后一个小于b\[i\]的数的下标,这里我们记做l.在再c数组中寻找第一个大于b\[i\]的数的下标,这里我们记做r。  
**3**.可知a数组中,小于b\[i\]的数的个数为l+1,c数组中大于b\[i\]数的个数为n-r.(下标从0开始)因此在三元递增组中,以b\[i\]为中间数的个数为(l+1) \* (n-r).  
**4**.遍历b数组,res+=(l+1) \* (n-r) 即为答案

### 3.代码 ###

**加粗样式**

#include<iostream>
    #include<algorithm>
    using namespace std;
    typedef long long LL;
    const int N=1e5+10;
    int a[N],b[N],c[N];
    int main()
    { 
        int n;
        scanf("%d",&n);
        for(int i=0;i<n;i++)  scanf("%d",&a[i]);
        for(int i=0;i<n;i++)  scanf("%d",&b[i]);
        for(int i=0;i<n;i++)  scanf("%d",&c[i]);
        sort(a,a+n);  //二分需要满足单调性
        sort(b,b+n);
        sort(c,c+n);
        LL res=0;  //答案可能会很大,会爆int
        for(int i=0;i<n;i++)
        { 
            int l=0,r=n-1;  //二分查找a数组中最后一个小于b[i]的数的下标
            while(l<r)
            { 
                int mid=(l+r+1)/2;
                if(a[mid]<b[i])   l=mid;
                else   r=mid-1;
            }
            if(a[l]>=b[i])   //如果未找到小于b[i]的数,将x标记为-1,后续计算时 x+1==0
            { 
                l=-1;       
            }
            int x=l;        
            l=0,r=n-1;
            while(l<r)
            { 
                int mid=(l+r)/2; 
                if(c[mid]>b[i])   r=mid;
                else  l=mid+1;
            }
            if(c[l]<=b[i])   //如果未找到大于b[i]的数,将y标记为n,后续计算时 n-y==0;
            { 
                r=n;
            }
            int y=r;
            res+=(LL)(x+1)*(n-y);
        }
        printf("%lld\n",res);
        return 0;
    }