【算法】求解满足条件整数对(C++源码)
一、问题描述
给定N个整数Ai以及一个正整数C,问其中有多少对i,j满足Ai–Aj=C?
二、输入描述
第1行输入两个空格隔开的整数N和C,第2~N+1行每行包含一个整数Ai
三、输出描述
输出满足条件的i,j对的数量例如:当N=5,C=3,A1~A5:2,1,4,2,5时,输出为3
四、步骤描述
做了两种方法,一种是直接暴力求解,时间复杂度为O(n²),第二种是先排序后直接排除小于差的数,时间复杂度为O(nlogn)
五、运行结果截图
六、源代码(C++)
//#include<iostream>
//#include<cmath>
//
//using namespace std;
//
//int main()
//{
// int n,c,count=0;
// cout<<"N = ";
// cin>>n;
// cout<<"C = ";
// cin>>c;
// int a[n];
// for(int i=0;i<n;i++)
// {
// cin>>a[i];
// }
// for(int i=0;i<n-1;i++)
// {
// for(int j=i+1;j<n;j++)
// {
// if(abs(a[i]-a[j])==c)
// {
// count++;
// }
// }
// }
// cout<<"The number of logarithms satisfying the condition is : "<<count<<endl;
// return 0;
//}
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int n,c,count=0;
cout<<"N = ";
cin>>n;
cout<<"C = ";
cin>>c;
int a[n];
for(int i=0;i<n;i++)
{
cin>>a[i];
}
sort(a,a+n);
for(int i=n-1;i>=0;i--)
{
for(int j=i-1;j>=0;j--)
{
if((a[i]-a[j])>c)
{
continue;
}
if((a[i]-a[j])==c)
{
count++;
}
}
}
cout<<"The number of logarithms satisfying the condition is : "<<count<<endl;
return 0;
}