题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5178

pairs

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3090 Accepted Submission(s): 1085

Problem Description

John has n 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≤109).
Next n lines
contain an integer x[i](−109≤x[i]≤109),
means the X coordinates.

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

题解：

两个要求：1:b>a 2.abs(x[b]-x[a])<=k。

先对数组进行排序。对于满足上述条件的a、b（ab为排序前的序号）来说。a、b的关系是可以互相转化的：

当abs(x[b]-x[a])<=k 且 b>a时，那这一对a、b固然满足条件。

当abs(x[b]-x[a])<=k 且 a>b时，那a就变成b，b就变成a，所以也满足条件。

综上，只需要找到abs(x[b]-x[a])<=k 的a、b对即可，无所谓ab的大小关系。但是直接这样计算会出现重复，正确的做法是，只取一边，即：x[a]+k或者是 x[a]-k，这样就能避免重复。

代码如下：

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #include <vector>

 #include <cmath>

 #include <queue>

 #include <stack>

 #include <map>

 #include <string>

 #include <set>

 #define rep(i,s,t) for(int (i)=(s); (i)<=(t); (i)++)

 #define ms(a,b) memset((a),(b),sizeof((a)))

 using namespace std;

 typedef long long LL;

 const int INF = 2e9;

 const LL LNF = 9e18;

 const double eps = 1e-;

 const int mod = 1e9+;

 const int maxn = 1e5+;

 int n, k;

 int a[maxn];

 int sch(int x)

 {

     int l = , r = n;

     while(l<=r)

     {

         int mid = (l+r)>>;

         if(a[mid]<=x)

             l = mid + ;

         else

             r = mid - ;

     }

     return r;

 }

 int main()

 {

     int T;

     scanf("%d",&T);

     while(T--)

     {

         scanf("%d%d",&n,&k);

         rep(i,,n)

             scanf("%d",&a[i]);

         sort(a+,a++n);

         LL ans = ;

         rep(i,,n-)

         {

             int p = sch(a[i]+k);

 //            int p = upper_bound(a+1,a+1+n,a[i]+k) - (a+1);

             ans += p-i;

         }

         printf("%I64d\n",ans);

     }

 }

巴特西

HDU 5178 pairs —— 思维 + 二分

pairs

最新文章

热门文章