AcWing 1236. 递增三元组(模板二分的应用）原题链接中等

作者：

田所浩二 , 2019-12-24 22:36:22 , 所有人可见 , 阅读 4071

16

7

题目描述

题目描述不再赘述，只想写一下菜鸡我遇到的坑
1.首先排序，对ac数组进行即可
2.a对于b数组，找的是小于b[i]的最大值，因此l=mid；之后再l+1算出a的数量|二者均是因为
3.c对于a数组，找的是大于a[i]的最小值，因此r=mid；之后再n-r算出c的数量|下标是从0开始
4.个人认为掌握了这道题二分就差不多了
5感谢@胡图图大佬，最后乘积时加ill，以及mul加long long

样例

输入样例：
3
1 1 1
2 2 2
3 3 3
输出样例：
27

算法1

#include<bits/stdc++.h>
using namespace std;
const int N=110000;
int a[N],b[N],c[N];
int n;
long long int mul;
int main()
{
    cin>>n;
    for(int i=0;i<=n-1;i++)
    {
        cin>>a[i];
    }
    for(int i=0;i<=n-1;i++)
    {
        cin>>b[i];
    }
    for(int i=0;i<=n-1;i++)
    {
        cin>>c[i];
    }
    sort(a,a+n);
    sort(b,b+n);
    sort(c,c+n);
    long long int mul=0;
    int left,right;
    for(int i=0;i<=n-1;i++)
    {
        int l=0,r=n-1;
        while(l<r)
        {
            int mid=l+r+1>>1;
            if(a[mid]<b[i])
            {
                l=mid;
            }
            else
            {
                r=mid-1;
            }
        }
        //cout<<l<<endl;
        if(a[l]>=b[i])
        {
            l=-1;
        }
        left=l;
        //cout<<res1<<endl;
        l=0,r=n-1;
        while(l<r)
        {
            int mid=l+r>>1;
            if(c[mid]>b[i])
            {
                r=mid;
            }
            else
            {
                l=mid+1;
            }
        }
        if(b[i]>=c[r])
        {
            r=n;
        }
        right=r;
        mul+=1ll*(n-right)*(left+1);
    }
    printf("%lld\n",mul);
    return 0;
}

33 评论

Yeah_ 2022-03-25 10:08

我无语了。。在线求助！我按照理解的二分思路把代码敲了一遍，其中一个测试数据是n=100000通不过，提示我是超时了，我反复改，改输入改输出也还是通不过，我又不觉得思路有啥问题，然后，我就把题解里的代码直接粘进去，结果，它是Finished了，可输出就是0啊，还是不是最后结果，这是为啥啊！！

bryant_Lin 2022-03-25 13:44

我也是手写二分，n=100000的数据直接等于0了，救命

bryant_Lin 2022-03-25 13:49 回复了 bryant_Lin 的评论

啊随手提交了结果AC了。。。。但是我那个数据。。。

Yeah_ 2022-03-26 16:34 回复了 bryant_Lin 的评论

我还是这样啊，要咋搞啊！！！

bryant_Lin 2022-03-26 17:28 回复了 Yeah_ 的评论

啊我直接ac了就没管了，你可以康康我写的题解代码

爱吃橙子 10个月前回复了 Yeah_ 的评论

最后mul还要乘上1ll，我也是和你一样的错误，看作者这样写了

爱吃橙子 10个月前回复了 Yeah_ 的评论

这就是一个强制转换，不至于溢出

Lukesu 2022-03-26 17:51

有点没看懂

mul+=1ll(n-right)(left+1);

希望大佬解释下QwQ

hongk_bb 2022-03-01 20:47

if(a[l]>=b[i])
{
l=-1;
}
left=l; if(b[i]>=c[r])
{
r=n;
}
right=r;

这两个判断是最终找到答案是否符合 a[i] < b[i] < c[i]
就好比说，a里面是5 6 7，而b里面是 1 1 1，那么二分的时候发现任何一个答案都不符合a[i] < b[i] ,那么我们就需要返回0，而这里的代码返回-1，是为了返回mul+=1ll(n-right)(left+1); 使该式所赋值为 -1 + 1 也就是0.后面的分析同理，不再赘述。

玛卡巴卡呀 2021-03-04 16:59

if(a[l]>=b[i])
{
l=-1;
}
left=l; if(b[i]>=c[r])
{
r=n;
}
right=r;请问这两段怎么理解呢没看明白

Jäger 2021-03-21 17:15

同问

玛卡巴卡呀 2021-03-21 21:56 回复了 Jäger 的评论

哈哈哈哈，我理解了，这两个if判断语句就是说当二分的while循环终止的时候，L=R,判断a[L]是否是小于b[j]的，如果是那么当前的L就是所得到的下标，如果不是的话，应该让L=-1(这个要看数组下标开始是1还是0了)，然后再不符合条件的情况下，计算左半部分和右半部分的乘积的时候结果为0

Summer_5 2021-04-03 15:55 回复了玛卡巴卡呀的评论

正常二分不都是（l+r）/2吗，这里为什么是l+r+1>>1，多加了个1？？你理解这里吗

玛卡巴卡呀 2021-04-03 17:09 回复了 Summer_5 的评论

建议看一下y总的二分课程，你就明白了

Summer_5 2021-04-04 16:28 回复了玛卡巴卡呀的评论

你说的这个课程在bilibili上吗

玛卡巴卡呀 2021-03-04 16:39

个数的话为什么不能在while循环里面直接判断出来呢？我这么写的直接超时什么结果都没有这是怎么回事？

麋鹿是森林的眼睛 2020-04-09 14:17

其实直接用lower_bound就行

小张同学 2020-03-06 10:06

同问！！！

小张同学 2020-03-06 10:08

if(b[i]>=c[r])
{
r=n;
}
right=r;
不是最大的都比b[i]小，那不应该 r = 0吗

Jordan 2020-02-12 23:33

if(a[l]>=b[i])
{
l=-1;
}
left=l; if(b[i]>=c[r])
{
r=n;
}
right=r;请问这两段怎么理解呢没看明白

阳光与你 2020-02-01 16:57

您能看看我的代码吗？我不知道哪错了，可以私信吗

田所浩二 2020-02-02 07:16

我尽力

阳光与你 2020-02-02 11:29 回复了田所浩二的评论

昨天弄出来了谢谢了

理性与感性的完美结合体 2020-01-31 22:12

也就是说想请教一下您这个二分是怎么理解的，我直接套y总的那个模板还是理解不太清楚。。。。

田所浩二 2020-02-01 08:58

我觉得我回答您这一个问题就好：二分分的是一个满足某个条件的区间，也就是说通过二分我们能把这个区间的左右端点找出来：诸如巧克力中我们要满足能分k个人，机器人跳跃中的必须能跳过去，我们必须要在满足这个的条件下进行二分，而分的类型又有不同：像y总讲课不是把二分分为红绿两端了吗，而红段的右端点就相当于所求区间的左端点也就是求最小值（对应讲课的模板1），绿段的左端点相当于所求区间的右端点也就是求所谓的最大值对应讲课中的模板二），二者的不同就是在于是l=mid还是r=mid，这俩决定了谁是所谓的红段谁是所谓的绿段（个人感悟，仅供参考）

理性与感性的完美结合体 2020-02-01 10:31 回复了田所浩二的评论

不知道我可不可以这样理解

while(l<r)
        {
            int mid=l+r+1>>1;
            if(a[mid]<b[i])
            {
                l=mid;
            }
            else
            {
                r=mid-1;
            }
        }

因为a[mid][HTML_REMOVED]=b[i]，b[i]在a[mid]的左边区间就要往左缩小，又因为我想找的是a里面比b[i]小的最后一个元素，但是又不能等于b[i]，所以mid要减1，r = mid - 1，然后对应的l = mid，然后再l + r + 1 >> 1
就是想请教您，我看到比如说要找一个递增数列里面小于某个值的二分的时候怎么去划分区间
说实话y总那个红绿端点我有点理解不了我觉得y总没说清楚二分的那个红色端点和绿色端点分别表示的是什么意思？
比如一条线段左边红色右边绿色，中间有个红色端点和绿色端点
那我如果要找绿色端点是代表什么意思呢？找到绿色端点就对应着小于目标值的最后一个端点或者是大于等于目标值的第一个端点了么？Orz

理性与感性的完美结合体 2020-02-01 10:35 回复了理性与感性的完美结合体的评论

前面没显示出来的是”因为a[mid]小于b[i]，没有等于号，所以我看else里面的a[mid]大于等于b[i]”

田所浩二 2020-02-01 10:45 回复了理性与感性的完美结合体的评论

1.如果只是找递增数列的话直接二分中点就可以啦，如果和实际问题挂钩那么就需要if（实际问题）
2.我认为是大于等于目标值的第一个端点

理性与感性的完美结合体 2020-01-31 22:04

但是很蛋疼，第一个样例里面1 1 1 1 1全是1就不知道怎么处理比较好，我特判之后的话还会有别的样例报错。。。

理性与感性的完美结合体 2020-01-31 22:02

就比如第一个a[mid]<b[i] 我理解的是要找的数就在mid的右边，区间向右缩小然后又因为是a[mid]<b[i]没有等于号就是l = mid + 1照着y总那个二分的模板套的
然后

//求大于等于target的第一个数的下标
   while(L < R)
    {
        int mid = L + R >> 1;
        if(num[mid] < target) L = mid + 1;
        else R = mid;
    }

然后在A中求出第一个大于等于target的数的下标-1就是小于target的最后一个数的下标

理性与感性的完美结合体 2020-01-31 21:59

想问一下您那两个二分分别表示的什么意思？

1.01 2019-12-25 17:51

秒懂，谢谢你的分享

田所浩二 2019-12-28 13:51

我也是想了好久才思考出来的

AcWing 1236. 递增三元组(模板二分的应用） 原题链接 中等

题目描述

样例

算法1

33 评论

mul+=1ll(n-right)(left+1);

AcWing 1236. 递增三元组(模板二分的应用）原题链接中等