HDU 5178 pairs（尺取法）

柔情只为你懂 2022-01-23 11:31 224阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY2NzYxMQ_size_16_color_FFFFFF_t_70]

**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;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY2NzYxMQ_size_16_color_FFFFFF_t_70]: /images/20220123/c48d3f914e134f47bb81bfe454aa8be5.png

发表评论取消回复

表情：

评论列表（有 0 条评论，224人围观）

还没有评论，来说两句吧...

相关阅读

相关 Hdu5178

Hdu5178 题意： > 题目给你N个点，问有多少对点的长度小于K 。解法： > 首先将所给的坐标从大到小排序，则此题转化为：对排序后的新数列，...

た入场券/ 2024年04月20日 10:24/ 0 赞/ 53 阅读

相关尺取法总结

一般地，当我们要去枚举满足条件的区间权值的区间，可以用遍历双指针 l 和 r 的做法去枚举第一个满足条件的区间，然后去维护其他数据，这样的做法就是尺取法，它的复杂度为O(n)

矫情吗；*/ 2024年03月31日 15:50/ 0 赞/ 74 阅读

相关尺取法模板

题目描述博览馆正在展出由世上最佳的 M 位画家所画的图画。 wangjy想到博览馆去看这几位大师的作品。可是，那里的博览馆有一个很奇怪的规定，就是在购买门票

迈不过友情╰/ 2023年10月11日 10:42/ 0 赞/ 66 阅读

相关尺取法：PIPI的目标Ⅲ

尺取法：PIPI的目标Ⅲ 文章目录尺取法：PIPI的目标Ⅲ 问题：思路：代码：问题：

深藏阁楼爱情的钟/ 2023年10月06日 21:58/ 0 赞/ 30 阅读

相关算法--尺取法

尺取法尺取法通常是指对数组保存一对下标（起点，终点），然后根据实际情况交替推进两个端点直到得出答案的方法，这种操作很像是尺取虫爬行的方式故得名。我们先来看看POJ的

￡神魔★判官ぃ/ 2022年08月21日 02:08/ 0 赞/ 192 阅读

相关 POJ 3601-Subsequence【尺取法】

Subsequence <table> <tbody> <tr> <td><strong>Time Limit:</strong> 1000MS<

- 日理万妓/ 2022年08月20日 09:29/ 0 赞/ 170 阅读

相关 poj3320 尺取法~~

Jessica's Reading Problem <table> <tbody> <tr> <td><strong>Time Limit:</strong

红太狼/ 2022年08月09日 00:44/ 0 赞/ 181 阅读

相关 POJ 3061 Subsequence（尺取法）

> Subsequence > Time Limit: 1000MS Memory Limit: 65536K > Total Submissions: 14595 A

梦里梦外;/ 2022年06月16日 07:24/ 0 赞/ 210 阅读

相关 POJ-3061.Subsequence(尺取法）

[3061.Subsequence][] 描述给出N个正整数（10 <N <100 000）的序列，每个正整数小于或等于10000，并且给出正整数S（S <100

小灰灰/ 2022年03月01日 17:18/ 0 赞/ 206 阅读

相关 HDU 5178 pairs（尺取法）

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

柔情只为你懂/ 2022年01月23日 11:31/ 0 赞/ 225 阅读