欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  移动技术

18728 数对问题二

程序员文章站 2022-05-21 12:37:59
时间限制:1000MS 代码长度限制:10KB提交次数:0 通过次数:0题型: 编程题 语言: 不限定Description此题目与数对问题一的唯一区别为序列中元素的取值范围。一个长度为N的正整数序列,现在需要计算出有多少对数字的差的绝对值为C。注意只要位置不同就认为是不相同的数对。输入格式第一行,两个整数 N, C。(1=

时间限制:1000MS 代码长度限制:10KB
提交次数:0 通过次数:0

题型: 编程题 语言: 不限定
Description
此题目与数对问题一的唯一区别为序列中元素的取值范围。
一个长度为N的正整数序列,现在需要计算出有多少对数字的差的绝对值为C。
注意只要位置不同就认为是不相同的数对。

输入格式
第一行,两个整数 N, C。(1=<N<=10000),(1=<C<=10000)
第二行,N个正整数a1…an。 ai为int范围内的正整数。

输出格式
仅一行,满足条件的数对的个数。

输入样例
4 1
1 2 3 1

输出样例
3

提示
(a1,a2),(a2,a3),(a2,a4)共3个数对满足条件。

分析:

这道题可以用哈希表做,但如果用stl的map容器做会更容易,相当于一个动态的二维计数数组,简单粗暴。

代码:

#include <iostream>
#include <map>
using namespace std;
int main(void)
{
	ios::sync_with_stdio(0),cin.tie(0);
	int i,j,k,sum=0,a[20010],n,c;
	cin>>n>>c;
	map<int,int>mp;
	for(i=1;i<=n;i++)
	{
		cin>>a[i];
		mp[a[i]]++;
	}
	for(i=1;i<=n;i++)
	{
		sum+=mp[a[i]+c];
		sum+=mp[a[i]-c];
	}
	cout<<sum/2;
	return 0;
} 

本文地址:https://blog.csdn.net/remakeprogramer/article/details/107168225