【2015南海小學】差(dec)
(File IO): input:dec.in output:dec.out
題目描述
楠楠在網上刷題，感覺第一題：求兩數的和(A+B Problem)太無聊了，于是增加了一題：A-B Problem，難倒了一群小朋友，哈哈，
題目是這樣的：給出N 個從小到大排好序的整數，一個差值C，要求在這N個整數中找兩個數A 和B，使得A-B=C，問這樣的方案有多少種？
例如：N=5，C=2，5 個整數是：2 2 4 8 10，答案是3，具體方案：第3 個數減第1 個數；第3 個數減第2個數；第5 個數減第4 個數，
輸入
第一行2 個正整數：N,C，
第二行N 個整數：已經有序，注意：可能有相同的，
輸出
一個整數，表示該串數中包含的所有滿足A-B=C 的數對的方案數，
樣例輸入
4 1
1 1 2 2
樣例輸出
4
資料范圍限制
5 個資料：N 的范圍是[1…1,000]，
5 個資料：N 的范圍是[1…100,000]，
所有資料：
C 的范圍是[1…1,000,000,000]，
N 個整數中每個數的范圍是：[0…1,000,000,000]，
哈！這不是水題嗎？
第一眼：列舉
（N 的范圍是[1…100,000]）……
第二眼：桶
（N 個整數中每個數的范圍是：[0…1,000,000,000]）……
…………
這里介紹兩種方法
第一種：分治（朋友們是否注意到了“已經有序”這四個字？）
先列舉1~N中的所有整數，再用二分的方法尋找第一個與最后一個相差C的值的位置，ans每次累加相差C的對數，最后得出結果，
#include<cstdio>
int n,c,a[100005];
long long ans;//千萬千萬不要忘了，ans是long long !!!!
int findl(int x)
{
int l=1,r=n;
while(l<=r)
{
int mid=(l+r)/2;
if(a[mid]>=x)
{
r=mid-1;
}
else
{
l=mid+1;
}
}
if(a[l]!=x) return 1;
else return l;
}
int findr(int x)
{
int l=1,r=n;
while(l<=r)
{
int mid=(l+r)/2;
if(a[mid]>x)
{
r=mid-1;
}
else
{
l=mid+1;
}
}
if(a[r]!=x) return 0;
else return r;
}
int main()
{
freopen("dec.in","r",stdin);
freopen("dec.out","w",stdout);
scanf("%d%d",&n,&c);
for(int i=1;i<=n;++i)
{
scanf("%d",&a[i]);
}
for(int i=1;i<=n;++i)
{
ans+=findr(a[i]+c)-findl(a[i]+c)+1;
//當找不到值為a[i]+c的數時，findr回傳0，findl回傳1，0-1+1=0
}
printf("%lld",ans);
return 0;
}
第二種：哈希（不會哈希的可以查一下資料）
用h陣列標記，同時用hg陣列記錄個數，hg[hash(i)]表示a陣列中值為i的數的個數，s每次累加hg[hash(a[i]+c)]，得出結果，
#include<cstdio>
const int m=400007;
long long h[m+2],hg[m+2],n,c,s,a[1000000];
int hash(long long x)
{
int y=x%m;//注意! N個整數中每個數的范圍是：[0…1,000,000,000] 而非[1…1,000,000,000]
while(h[y]!=0&&h[y]!=x)
{
y++;
if(y>=m) y=0;
}
return y;
}
int main()
{
freopen("dec.in","r",stdin);
freopen("dec.out","w",stdout);
scanf("%lld%lld",&n,&c);
for(int i=1;i<=n;++i)
{
scanf("%lld",&a[i]);
int hh=hash(a[i]);
h[hh]=a[i];
hg[hh]++;
}
for(int i=1;i<=n;++i)
{
int hh=hash(a[i]+c);
s+=hg[hh];
}
printf("%lld",s);
return 0;
}
小朋友：啊！真的難倒我了！
father：這都不會，打！
（啪！……啪！……）
不見不散！
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/258824.html
標籤：其他
上一篇：深入理解采樣定理 + Matlab 仿真 Sa 函式的采樣與恢復
下一篇：第一篇接觸Java