pairs??HDU - 5178?

John has?nn?points on the X axis, and their coordinates are?(x[i],0),(i=0,1,2,…,n?1) He wants to know how many pairs<a,b> that?|x[b]?x[a]|≤k.(a<b)

Input

The first line contains a single integer?T?(about 5), indicating the number of cases.?
Each test case begins with two integers?n,k(1≤n≤100000,1≤k≤10^9)
Next?nn?lines contain an integer?x[i](?109≤x[i]≤10^9)

Output

For each case, output an integer means how many pairs<a,b>,that?|x[b]?x[a]|≤k

Sample Input

2 5 5 -100 0 100 101 102 5 300 -100 0 100 101 102

Sample Output

3 10

題意：

有N個數組成的序列，問有多少對<a,b>滿足|x[b]?x[a]|≤k.(a<b)，去掉絕對值即 x[a]-k ≤ x[b] ≤ x[a]-k (a<b)，枚舉前面一個點，然后二分查找即可

#include<bits/stdc++.h> using namespace std; const int maxn=1e5+10; typedef long long LL; LL x[maxn]; int n; LL k; int main(){int T;scanf("%d",&T);while(T--){scanf("%d%lld",&n,&k);for(int i=1;i<=n;i++){scanf("%lld",&x[i]);}sort(x+1,x+1+n);LL ans=0;for(int i=1;i<=n;i++){int l=lower_bound(x+i+1,x+1+n,x[i]-k)-(x+1);int r=upper_bound(x+1+i,x+1+n,x[i]+k)-(x+1);ans+=(r-l);}printf("%lld\n",ans);}return 0; }

直接查找下界即可

#include<bits/stdc++.h> using namespace std; const int maxn=1e5+10; typedef long long LL; LL x[maxn]; int n; LL k; int main(){int T;scanf("%d",&T);while(T--){scanf("%d%lld",&n,&k);for(int i=1;i<=n;i++){scanf("%lld",&x[i]);}sort(x+1,x+1+n);LL ans=0;for(int i=1;i<=n;i++){int r=upper_bound(x+1+i,x+1+n,x[i]+k)-(x+1);ans+=(r-i);}printf("%lld\n",ans);}return 0; }

下標從0開始

# include <stdio.h> # include <algorithm> using namespace std;int a[100001]; int main() {int n, k, t;scanf("%d",&t);while(t--){scanf("%d%d",&n,&k);long long ans = 0;for(int i=0; i<n; ++i)scanf("%d",&a[i]);sort(a, a+n);for(int i=0; i<n-1; ++i){int pos = upper_bound(a+i,a+n, a[i]+k)-a;ans += pos - i - 1;}printf("%lld\n",ans);}return 0; }

尺取法

#include<bits/stdc++.h> using namespace std; const int maxn=1e5+10; typedef long long LL; LL x[maxn]; int n; LL k; int main(){int T;scanf("%d",&T);while(T--){scanf("%d%lld",&n,&k);for(int i=0;i<n;i++){scanf("%lld",&x[i]);}sort(x,x+n);LL ans=0;for(int l=0,r=0;l<n;++l){while(r+1<n&&x[r+1]-x[l]<=k) ++r;ans+=(r-l);}printf("%lld\n",ans);}return 0; }

?

總結

以上是生活随笔為你收集整理的HDU5178 pairs【二分法】【尺取法】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。