【尺取法】pairs

传送:这里

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

题意:给定一个数组,求有多少对<a,b>使得|x[b]−x[a]|≤k.(a<b)
思路:
先排序,然后i从0开始,从0开始判断,如果值小于等于k的话,tmp++,直到>k停止,ans加上该值。下一次,i+1,也可以,共加tmp-1次

代码:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
#include<cmath>
using namespace std;
#define N 100006
#define ll long long 
int n, k;
int a[N];
int main()
{
  int t;
  cin >> t;
  while (t--)
  {
    cin >> n >> k;
    for (int i = 0; i < n; i++)
      cin >> a[i];
    sort(a, a + n);
    ll ans = 0;
    int tmp = 0;
    for (int i = 0; i < n; i++)
    {
      while (abs(a[i] - a[tmp]) <= k && tmp < n) 
        tmp++;
      ans += (tmp - i - 1) ;
    }
    cout << ans << endl;
  }
  return 0;
}

 

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注

2 × 4 =