洛谷---P1102 A-B 数对---双指针算法

小咪咪 2024-03-26 12:41 44阅读 0赞

> **题目链接：**  
> [P1102 A-B 数对][P1102 A-B]  
> **题目描述：**  
> ![在这里插入图片描述][096c83e558174a7da38d6614b19ce0eb.png]

**双指针算法（快慢指针）算法**

#include<iostream>
    #include<algorithm>
    #include<cstdio>
    
    using namespace std;
    
    typedef long long ll;
    
    int n,c;
    int arr[200020];
    
    int main()
    {
        
        scanf("%d %d",&n,&c);
        
        for(int i=1;i<=n;++i) cin>>arr[i];
        
        sort(arr+1,arr+1+n);
    	//对输入的数组进行排序
        
        ll res=0;//因为数据使用int会撑爆，所以用ll
        //三个指针：快指针a，慢指针b1,b2;
        for(int a=1,b1=1,b2=1;a<=n;++a)
        {
        
            while(b1<=a && arr[a]-arr[b1]>=c ) b1++;
            
            while(b2<=a && arr[a]-arr[b2]>c ) b2++;
            
            res+=b1-b2;
    
        }
        printf("%lld",res);
        
        return 0;
    }

总结：**自己需要多模拟以及多练习这些题目，自己写还是写不出来的。**

[P1102 A-B]: https://www.luogu.com.cn/problem/P1102
[096c83e558174a7da38d6614b19ce0eb.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/d34bcb61b79249299aab5989d511903e.png

发表评论取消回复

表情：

评论列表（有 0 条评论，44人围观）

还没有评论，来说两句吧...

相关阅读

相关洛谷---P1102 A-B 数对---双指针算法

> 题目链接： > [P1102 A-B 数对][P1102 A-B] > 题目描述： > ![在这里插入图片描述][096c83e558174a7da38d661

小咪咪/ 2024年03月26日 12:41/ 0 赞/ 44 阅读

相关 P1102 A-B 数对

[洛谷P1102 A-B 数对][P1102 A-B] 题目描述出题是一件痛苦的事情！相同的题目看多了也会有审美疲劳，于是我舍弃了大家所熟悉的 A+B Probl

╰半夏微凉°/ 2023年01月18日 09:18/ 0 赞/ 89 阅读

相关洛谷 P1205数的划分

P1025 数的划分题目描述将整数n分成k份，且每份不能为空，任意两个方案不相同(不考虑顺序)。例如：n=7，k=3，下面三种分法被认为是相同的。 1，1

谁借莪１个温暖的怀抱￠/ 2022年07月15日 11:17/ 0 赞/ 165 阅读

相关洛谷 P1205数的划分

P1025 数的划分题目描述将整数n分成k份，且每份不能为空，任意两个方案不相同(不考虑顺序)。例如：n=7，k=3，下面三种分法被认为是相同的。 1，1

迈不过友情╰/ 2022年07月15日 11:17/ 0 赞/ 196 阅读

相关洛谷P1036 选数

题目描述已知 n 个整数 x1,x2,…,xn，以及一个整数 k（k＜n）。从 n 个整数中任选 k 个整数相加，可分别得到一系列的和。例如当 n=4，k＝3，4 个整

我会带着你远行/ 2022年06月01日 11:24/ 0 赞/ 241 阅读

相关洛谷P1012 拼数

题目描述设有n个正整数（n≤20），将它们联接成一排，组成一个最大的多位整数。例如：n=3时，3个整数13，312，343联接成的最大整数为：34331213 又

╰半夏微凉°/ 2022年05月31日 10:17/ 0 赞/ 206 阅读

相关洛谷P1045 麦森数

题目描述形如2^\{P\}-12P−1 的素数称为麦森数，这时PP 一定也是个素数。但反过来不一定，即如果PP 是个素数，2^\{P\}-12P−1 不一定也是素数。到

小鱼儿/ 2022年05月30日 11:08/ 0 赞/ 206 阅读

相关洛谷P1908 逆序对

题目描述猫猫TOM和小老鼠JERRY最近又较量上了，但是毕竟都是成年人，他们已经不喜欢再玩那种你追我赶的游戏，现在他们喜欢玩统计。最近，TOM老猫查阅到一个人类称之为“

客官°小女子只卖身不卖艺/ 2022年05月30日 06:44/ 0 赞/ 184 阅读

相关洛谷P1255 数楼梯

题目描述楼梯有N阶，上楼可以一步上一阶，也可以一步上二阶。编一个程序，计算共有多少种不同的走法。输入输出格式输入格式：一个数字，楼梯数。输

Dear 丶/ 2022年05月26日 08:11/ 0 赞/ 196 阅读

相关洛谷 P1028 数的计算

嗯... 首先这道题想到的就是递推.... 但是递推失败（不知道自己是怎么想的然后又想打一个暴力，但是数的最高位太难存储了，所以又放弃了（并且好

绝地灬酷狼/ 2022年01月11日 07:15/ 0 赞/ 431 阅读