LuoguP2421
原题来自NHOI2015
【解题思路】
本题的解题方法有三种,一种为枚举减数,二分查找被减数。第二种为利用数据单调性用尺取法进行查找,第三种为运用哈希表以快速查找数据。
【解题反思】
- 一题可能有多种解法,尝试选择自己最擅长的。
【参考程序】
#include<iostream>
#include<cstdio>
using namespace std;
int n,a[100001],i,j,ans,s,c;
int main()
{
freopen("dec.in","r",stdin);
freopen("dec.out","w",stdout);
cin>>n>>c;
for (int k=1;k<=n;k++) cin>>a[k];
i=1;
j=i+1;a[i-1]=-1;
while (i<=n)
{
if (a[j]-a[i]<c)//如果差值小了,那么增大被减数
{
j++;
}
else if (a[j]-a[i]>c||j>n)//如果差值大了,那么增大减数
{
i++;
if (a[i]==a[i-1]) ans+=s;//如果与前一个统计的相同,意味着无需再次统计
else s=0;
}
else if (a[j]-a[i]==c)//如果相等,那么统计并且增大被减数
{
j++;
ans++;
s++;
}
}
cout<<ans;
return 0;
}
以上是尺取法
#include<iostream>
#include<cstdio>
using namespace std;
int a[100001];
int n,c,ans,b,tmp;
int main()
{
freopen("dec.in","r",stdin);
freopen("dec.out","w",stdout);
cin>>n>>c;
int j=1;
for (int i=1;i<=n;i++) cin>>a[i];
for (int i=1;i<=n;i++)
{
int l=0,r=n+1,mid;
while (l<r-1)
{
mid=(l+r)/2;
if (a[mid]-a[i]>=c) r=mid;
if (a[mid]-a[i]<c) l=mid;
}//查找被减数在数据中最开始的位置
tmp=r;
l=0;r=n+1;
while (l<r-1)
{
mid=(l+r)/2;
if (a[mid]-a[i]<=c) l=mid;
if (a[mid]-a[i]>c) r=mid;
}//查找被减数在数据中最后出现的位置
ans+=l-tmp+1;//统计
}
cout<<ans;
return 0;
}
上为二分查找法
#include<iostream>
#include<cstdio>
using namespace std;
const int mod=1000007;
int hash[mod+5],count[mod+5],n,c,ans,a[100001];
void add(int s)//将该数压入哈希表
{
int cod=s%mod;
while (hash[cod]!=s&&hash[cod]!=0)//线性探测法解决哈希表冲突
{
cod++;
cod%=mod;
}
hash[cod]=s;
count[cod]++;
}
int find(int s)//在哈希表中寻找该数值
{
int cod=s%mod;
while (hash[cod]!=s&&hash[cod]!=0)//线性探测
{
cod++;
cod%=mod;
}
if (hash[cod]==s) return cod;
else return 0;
}
int main()
{
freopen("dec.in","r",stdin);
freopen("dec.out","w",stdout);
cin>>n>>c;
for (int i=1;i<=n;i++)
{
cin>>a[i];
add(a[i]);
}
for (int i=1;i<=n;i++)
{
int p=find(a[i]+c);
if (p!=0) ans+=count[p];
}
cout<<ans;
return 0;
}
上为哈希表法