第九届蓝桥杯省赛C++B组递增三元组【二分】题解-白红宇的个人博客

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

发布日期：2021-05-07 08:50:10 浏览次数：24 分类：精选文章

本文共 1057 字，大约阅读时间需要 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

输入样例：

1 1 1

2 2 2

3 3 3

输出样例：

2.思路

思路:二分先对三个数组进行sort排序，然后遍历b数组,对于b中的每一个数b[i],在a数组寻找最后一个小于b[i]的数的下标，这里我们记做l.再在c数组中寻找第一个大于b[i]的数的下标,这里我们记做r。a数组中,小于b[i]的数的个数为l+1，c数组中大于b[i]数的个数为n-r。因此当在三元递增组中,以b[i]为中间数的个数为(l+1)*(n-r)。遍历b数组,累加即为答案。

3.代码

#include
   
    #include
    
     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
     
      =b[i])   //如果未找到小于b[i]的数,将x标记为-1,后续计算时 x+1==0        {               l=-1;               }        int x=l;                l=0,r=n-1;        while(l
      
       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;}