首页 > 其他分享 >p1102 A-B数对

p1102 A-B数对

时间:2022-12-01 20:44:27浏览次数:47  
标签:正整数 p1102 int 数对 样例 leq include

A-B 数对

题目背景

出题是一件痛苦的事情!

相同的题目看多了也会有审美疲劳,于是我舍弃了大家所熟悉的 A+B Problem,改用 A-B 了哈哈!

题目描述

给出一串正整数数列以及一个正整数 \(C\),要求计算出所有满足 \(A - B = C\) 的数对的个数(不同位置的数字一样的数对算不同的数对)。

输入格式

输入共两行。

第一行,两个正整数 \(N,C\)。

第二行,\(N\) 个正整数,作为要求处理的那串数。

输出格式

一行,表示该串正整数中包含的满足 \(A - B = C\) 的数对的个数。

样例 #1

样例输入 #1

4 1
1 1 2 3

样例输出 #1

3

提示

对于 \(75\%\) 的数据,\(1 \leq N \leq 2000\)。

对于 \(100\%\) 的数据,\(1 \leq N \leq 2 \times 10^5\),\(0 \leq a_i <2^{30}\),\(1 \leq C < 2^{30}\)。

2017/4/29 新添数据两组

思路

考虑到A-B=C情况可以转化为A-C=B,此时先将输入的情况排序,枚举每一个A的情况,如果存在第一个符合这一条件的数,定为左边;再找最后一个符合这一条件的数定为右边,ans加上r-l即可。

完整代码

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include<vector>
#include<queue>
#include<set>
#include<unordered_map>
using namespace std;
int n,c;
int a[200005]; 
int main(){
	long long ans=0;
	cin>>n>>c;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	
	sort(a+1,a+n+1);
	int r1=1;
	int r2=1;
	for(int i=1;i<=n;i++){
		while(r1<=n&&a[r1]-a[i]<c)
			++r1;
		while(r2<=n&&a[r2]-a[i]<=c)
			++r2;
		if(a[r1]-a[i]==c&&a[r2-1]-a[i]==c)
			ans+=r2-r1;
	}
	cout<<ans;
	return 0;
}

标签:正整数,p1102,int,数对,样例,leq,include
From: https://www.cnblogs.com/simdow/p/16942618.html

相关文章

  • 13 STL-函数对象
    ​ 重新系统学习c++语言,并将学习过程中的知识在这里抄录、总结、沉淀。同时希望对刷到的朋友有所帮助,一起加油哦! 每一次学习都是为了追求智慧!写在前面,本篇章主要介......
  • 关于C#函数对象参数传递的问题
      我们知道在.net里class是引用类型,在函数参数表中的对象传递的都是对象的引用,所以在函数体内对其对象参数的修改会影响函数外对应的对象本身,例如下面的程序:classProgr......
  • YACS 2022年11月月赛 乙组 T1 数对统计 题解
    好久没更了,闲话一句,我的初赛成绩只有$71.5$,$76$才能进$NOIP$,所以就更一篇吧首先先考虑暴力算法,枚举两个数,设这两个数为$x$和$y$,如果$f[x][y]=false$,那就标记为$t......
  • Git reset 的hard、soft、mixed参数对比
    目录分区概念1.--soft参数2.--mixed参数3.--hard参数分区概念先要清楚在本地,git会分三个区:工作区、暂存区、本地库。当使用去做版本移动的时候,那么在使用【--hard】......
  • C语言:亲密数对
    题目输入N,N在2至3000之间,求2至N中的亲密数对。所谓亲密数对,就是A的因子和等于B,B的因子和等于A,且A≠B。如48和75是亲密数对。48的因子和为2+3+4+6......
  • 表面粗糙度详解及参数对比表说明
    表面粗糙度详解及参数对比表说明来源https://zhuanlan.zhihu.com/p/115444210 表面粗糙度表面粗糙度(surfaceroughness)是指加工表面具有的较小间距和微小峰谷的不......
  • 函数对象
    4STL-函数对象4.1函数对象4.1.1函数对象概念概念:重载函数调用操作符()的类,其对象常称为函数对象函数对象使用重载的()时,行为类似函数调用,也叫仿函数本质:函......
  • 【速腾】23款速腾各版本参数对比
    速腾官网:一汽-大众全新速腾_全新速腾报价_配置_图片|一汽-大众品牌官网   ......
  • 数对数目
    题目给定一个长度为\(n\)的序列\(a_1,a_2,\ldots,a_n\)。请你找出一共有多少个数对\((i,j)\)满足\(a[i]\lti\lta[j]\ltj\,1\leqslanti,j\leqslantn\)......
  • 仿函数(函数对象)functor的用法
    引子在set的类模板中,插入元素是会自动排序的,那么这是如何实现的呢。默认的set<int> setl;这种写法,他会调用默认的less函数对象less函数对象实现比较,为排序提供依据,se......