Description
腾讯2017暑期实习生编程题 小Q今天在上厕所时想到了这个问题：有n个数，两两组成二元组，相差最小的有多少对呢？相差最大呢？
输入格式
N本组测试数据有n个数 a1,a2...an - 需要计算的数据 保证: 1<=n<=100000,0<=ai<=INT_MAX.
输出格式
输出两个数，第一个数表示差最小的对数，第二个数表示差最大的对数。
输入样例
6 45 12 45 32 5 6
输出样例
1 2
题目分析：找寻有多少对数字。和这个问题很接近。
| 18728 | 数对问题二（★★） |
当然这个题目要求找寻相差最大和相差最小的对数。哪也没关系，先求出相差最小和最大值就行了。
请记住：计算数对问题---------使用map来辅助。
#include <iostream>
#include<algorithm>
#include <map>
using namespace std;
int main()
{
int t,n,a[100005],i;
while(cin>>n)/**< 多组数组这样读取，读到结束标志就退出循环 */
{
int minv,maxv,minc=0,maxc=0;
for(i=1; i<=n; i++)
cin>>a[i];
sort(a+1,a+n+1);/**< 升序排序 */
minv=a[2]-a[1];
for(i=2; i<n; i++) /**< 求相差最小值 */
if(a[i+1]-a[i]<minv)
minv=a[i+1]-a[i];
/**< 用map统计数对 */
map<int,int>mp;
mp[a[1]]=1;
for(i=2;i<=n;i++)
{
minc+=mp[a[i]-minv];
mp[a[i]]++;
}
/**< 到此结束 */
mp.clear();
maxv=a[n]-a[1];/**< 最大值直接拿到 */
mp[a[1]]=1;
for(i=2;i<=n;i++)
{
maxc+=mp[a[i]-maxv];
mp[a[i]]++;
}
cout<<minc<<' '<<maxc<<endl;
}
return 0;
}
第二种方法：先排序求出最大值最小值，然后使用数据分析法。
最小值，最大值均存在多种情况需要分析考虑
#include <iostream>
#include<algorithm>
using namespace std;
int main()
{
int n,a[100005],i,minv,minc=0,cmin,cmax,same;
while(cin>>n)
{
for(i=1; i<=n; i++)
cin>>a[i];
sort(a+1,a+n+1);/**< 排序 */
minv=a[2]-a[1];
minc=1;
for(i=2; i<n; i++) /**< 求最小值，顺路求最小值对数 */
{
int t=a[i+1]-a[i];
if(t<minv)
minv=t,minc=1;
else if(t==minv)
minc++;
}
if(minv==0)/**< 如果最小值是0，这个时候不相邻元素也可能是最小值，重新求最小值对数*/
{
minc=0,same=1;
for(i=2; i<=n+1; i++)
{
if(a[i]==a[i-1])
same++;
else
{
minc+=same*(same-1)/2;
same=1;
}
}
}
cout<<minc<<' ';
for(i=2; i<=n; i++)/**< 最大值个数可以考虑此样例1 1 2 3 3 3，实际上是1和3搭配，共6对 */
if(a[i]!=a[1])
break;
cmin=i-1; /**< 先求出最小值多少个 */
for(i=n-1; i>=1; i--)
if(a[i]!=a[n])
break;
cmax=n-i;/**< 最大值多少个 */
if(cmin!=n) /**< 有一种特殊情况，n个值完全相同 */
cout<<cmin*cmax;
else
cout<<n*(n-1)/2;
cout<<endl;
}
return 0;
}