HDU 5178 pairs（尺取法）-蒲公英云

HDU 5178 pairs（尺取法）

在这里插入图片描述

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

Sample Output
3
10

题意：给你一段序列，让你找出满足 |x[b]−x[a]|≤k.(a<b)的个数。

题解：尺取法（日本有种动物叫尺取虫（同音字我忘了咋写了），类似于毛毛虫，要么头动，要么尾动，一直往一个方向运动）。
这个题把序列从小到大排序，给定两个变量i，j指向第一个值和第二个值，直到最后一个 j 指向末尾结束，开始如果 | a[j] - a[i] | >k 说明这个不满足，区间大了尾巴i 右移一位，如果满足了用一个s 统计下总和 s + = j - i 看看后面的值是否还满足，头右移一位 j++ ，跑到最后 j 到最后一位就结束了，注意，每次都统计的是一个区间。

AC代码：

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;
const int mmax=1e6+10;
int a[mmax],b[mmax];
int main()
{
    ios::sync_with_stdio(false);
    ll t;
    cin>>t;
    while(t--)
    {
        memset(a,0,sizeof(a));
        ll n,k;
        cin>>n>>k;
        for(int i=0;i<n;i++)
        {
            cin>>a[i];
        } 
        sort(a,a+n);
        ll i=0,j=1,s=0;
        while(j<n)
        {
            if(a[j]-a[i]>k)
                i++;
            else
            {
                s+=j-i;
                j++;
            }
        }
        cout<<s<<endl;
    }
    return 0;
}