P1102 A-B 数对

题目描述

出题是一件痛苦的事情！

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

好吧，题目是这样的：给出一串数以及一个数字 C，要求计算出所有 A-B=C 的数对的个数。（不同位置的数字一样的数对算不同的数对）

输入格式

第一行包括2个非负整数N和C，中间用空格隔开。

第二行有N个整数，中间用空格隔开，作为要求处理的那串数。

输出格式

输出一行，表示该串数中包含的所有满足A-B=C的数对的个数。

输入输出样例

输入 #1

4 1

1 1 2 3

输出 #1

说明/提示

对于73%73%的数据，N≤2000；

对于100%100%的数据，N≤200000。

所有输入数据都在longint范围内。

2017/4/29新添数据两组

【思路】

两种思路，用桶或者用双指针

【桶】

输入数据，用一个桶存一下

然后从1枚举到最大值

如果一个数出现过

并且他减去c的数也出现过

那么数对的数量就是

这两个数的桶里面存的值乘起来

最后加起来就好了

【完整代码】

#include<cstdio>

#include<iostream>

#include<map>

using namespace std;

int a[200005];//桶存储每个出现过的数的次数

map<int,int> tong;

int main()

{

	int n,c;

	scanf("%d%d",&n,&c);

	for(int i = 1;i <= n;++ i)

	{

		scanf("%d",&a[i]);

		tong[a[i]] ++;//计数

	}

	long long js = 0;

	for(int i = 1;i <= n;++ i)

 	{//这里倒着想不去找两个数而是找一个然后再找另一个

 		js += tong[a[i] + c];

	}

	printf("%lld\n",js);

	return 0;

 }

【双指针】

双指针

现将输入的那串数字排一下序

然从以一个开始枚举

头指针先不动

尾指针累加知道尾指针所在的位置上面的数

减去头指针所在的数的差大于等于c

然后判断是否等于c

如果等于c计数器累加

不过这道题目会出现重复的数

如果单纯的按照上面的方法是没法处理重复的数

所以可以在

当你找到一组差恒等于c的数的时候

判断一下大的后面还有没有也可以减去小的恒等于c的

也就是等于大的的

为什么不处理小的而是处理大的呢？

因为我的思路是枚举小的所以小的都会扫一遍

但是大的确实会跳过去的

所以应该处理大的

不过如果你处理出来有多少个和他相等的

那就用一个桶记录一下

到时候再一次用到的话直接O(1)查询就好

不然会超时

依次枚举下去

因为头指针和尾指针都是只将那串数字扫一遍

所以复杂度是线性的

【完整代码】

#include<iostream>

#include<cstdio>

#include<algorithm>

using namespace std;

const int Max = 200005;

int a[Max];

int t[Max];

int main()

{

	int n,c;

	cin >> n >> c;

	long long js = 0;

	for(register int i = 1;i <= n;++ i)

		cin >> a[i];

	sort(a + 1,a + 1 + n);

	for(register int l = 1,r = 1;l <= n;++ l)

	{

		while(a[r] - a[l] < c && r <= n)

			r ++;

		if(r > n)

			break;

		if(a[r] - a[l] == c)

		{

			int jj;

			if(t[r] != 0)

			{

				jj = t[r];

			}

			else

			{

				jj = 1;

				int rr = r + 1;

				while(a[rr] - a[l] == c)

					jj ++,rr ++;

				t[r] = jj;

			}

			js += jj;

		}

	}

	cout << js << endl;

	return 0;

}

【PS】

其实还有更简单的方法的

思路说一哈：

枚举大数A，用双指针法找到最靠前与A差≤ C的，和最靠后与A差≥ C的。如果这两个位置不是在同一个数上面，那么他们中间就是还有符合要求的数，所以这中间的数的个数（包括两个位置上面的）都累加起来。

但是貌似实现起来很复杂，只想出来了思路没有去实现瞎搞了一下搞了上面的思路然后A掉了QWQ

巴特西

洛谷 P1102 A-B数对题解

P1102 A-B 数对

题目描述

输入格式

输出格式

输入输出样例

说明/提示

【思路】

【桶】

【完整代码】

【双指针】

【完整代码】

【PS】

最新文章

热门文章

巴特西

洛谷 P1102 A-B数对 题解

P1102 A-B 数对

题目描述

输入格式

输出格式

输入输出样例

说明/提示

【思路】

【桶】

【完整代码】

【双指针】

【完整代码】

【PS】

最新文章

热门文章

洛谷 P1102 A-B数对题解