CCF认证--相邻数对

柔光的暖阳◎ 2022-05-14 09:04 164阅读 0赞

### 问题描述 ###

<table> 
 <tbody> 
  <tr> 
   <td>试题编号：</td> 
   <td>201409-1</td> 
  </tr> 
  <tr> 
   <td>试题名称：</td> 
   <td>相邻数对</td> 
  </tr> 
  <tr> 
   <td>时间限制：</td> 
   <td>1.0s</td> 
  </tr> 
  <tr> 
   <td>内存限制：</td> 
   <td>256.0MB</td> 
  </tr> 
  <tr> 
   <td>问题描述：</td> 
   <td> <p>问题描述</p> <p>　　给定n个不同的整数，问这些数中有多少对整数，它们的值正好相差1。</p> <p>输入格式</p> <p>　　输入的第一行包含一个整数n，表示给定整数的个数。<br> 　　第二行包含所给定的n个整数。</p> <p>输出格式</p> <p>　　输出一个整数，表示值正好相差1的数对的个数。</p> <p>样例输入</p> <p>6<br> 10 2 6 3 7 8</p> <p>样例输出</p> <p>3</p> <p>样例说明</p> <p>　　值正好相差1的数对包括(2, 3), (6, 7), (7, 8)。</p> <p>评测用例规模与约定</p> <p>　　1&lt;=n&lt;=1000，给定的整数为不超过10000的非负整数。</p> </td> 
  </tr> 
 </tbody> 
</table>

> ### 思路 ###
> 
> 利用set来存储，因为所给数据不重复，并且set里面的find()函数是用红黑树实现的，算法复杂度为O(logn)，效率很高，因此，所给的代码时间复杂度为O(n\*logn)
> 
> 此外，当a=b+1或者a=b-1时,a是b的相邻数对，b也是a的相邻数对，这样的话，便会重复统计，根据握手定理可知，最终的相邻数对是cnt/2.
> 
> ### 代码 ###
> 
>     #include<iostream>
>     #include<set>
>     using namespace std;
>     int main()
>     {
>     	int n;
>     	cin>>n;
>     	set<int> myset;
>     	int temp=0;
>     	for(int i=0;i<n;i++)
>     	{		
>     		cin>>temp;
>     		myset.insert(temp); 
>     	}
>     	set<int>::iterator it=myset.begin();
>     	int cnt=0;
>     	for(;it!=myset.end();it++)
>     	{
>     		if(myset.find(*it+1)!=myset.end())
>     		{
>     			cnt++;
>     		}
>     		if(myset.find(*it-1)!=myset.end())
>     			cnt++;	
>     	}
>     	cout<<cnt/2<<endl;
>     	return 0;
>     }
> 
>

发表评论取消回复

表情：

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

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

相关阅读

相关 C++程序设计：相邻数对

【问题描述】给定n个不同的整数，问这些数中有多少对整数，它们的值正好相差1。【输入形式】输入的第一行包含一个整数n，表示给定整数的个数。第二行包含所给定的n个

小咪咪/ 2022年12月02日 12:25/ 0 赞/ 74 阅读

相关问题 D: 相邻数对问题

题目描述给定n个不同的整数，问这些数中有多少对整数，它们的值正好相差1。评测用例规模与约定 1<=n<=1000，给定的整数为不超过10000的非负整数。

朴灿烈づ我的快乐病毒、/ 2022年06月10日 00:56/ 0 赞/ 129 阅读

相关 CCF认证--出现次数最多的数

问题描述 <table> <tbody> <tr> <td>试题编号：</td> <td>201312-1</td> </tr> <tr

约定不等于承诺〃/ 2022年05月14日 09:06/ 0 赞/ 158 阅读

相关 CCF认证--相反数

问题描述 <table> <tbody> <tr> <td>试题编号：</td> <td>201403-1</td> </tr> <tr

谁借莪１个温暖的怀抱￠/ 2022年05月14日 09:06/ 0 赞/ 161 阅读

相关 CCF认证--窗口

问题描述 <table> <tbody> <tr> <td style="width:92px;">试题编号：</td> <td>201403-2<

川长思鸟来/ 2022年05月14日 09:04/ 0 赞/ 136 阅读

相关 CCF认证--相邻数对

问题描述 <table> <tbody> <tr> <td>试题编号：</td> <td>201409-1</td> </tr> <

柔光的暖阳◎/ 2022年05月14日 09:04/ 0 赞/ 165 阅读

相关 CCF认证--图像旋转

> 问题描述 > > <table> > <tbody> > <tr> > <td>试题编号：</td> > <td>201503-1</td>

清疚/ 2022年05月14日 08:49/ 0 赞/ 178 阅读

相关 CSP201409-1：相邻数对

引言：CSP[（http://www.cspro.org/lead/application/ccf/login.jsp）][http_www.cspro.org_lead_ap

悠悠/ 2021年09月30日 11:02/ 0 赞/ 259 阅读

相关 2014-9-1相邻数对

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

小鱼儿/ 2021年09月21日 10:48/ 0 赞/ 253 阅读

相关 CCF 相邻数对

一、试题问题描述　　给定n个不同的整数，问这些数中有多少对整数，它们的值正好相差1。输入格式　　输入的第一行包含一个整数n，表示给定整数的个数。

怼烎@/ 2021年06月24日 15:57/ 0 赞/ 377 阅读