【bzoj2096】[Poi2010]Pilots 双指针法+STL-set
2024-09-29 03:40:54
题目描述
Tz又耍畸形了!!他要当飞行员,他拿到了一个飞行员测试难度序列,他设定了一个难度差的最大值,在序列中他想找到一个最长的子串,任意两个难度差不会超过他设定的最大值。耍畸形一个人是不行的,于是他找到了你。
输入
输入:第一行两个有空格隔开的整数k(0<=k<=2000,000,000),n(1<=n<=3000,000),k代表Tz设定的最大值,n代表难度序列的长度。第二行为n个由空格隔开的整数ai(1<=ai<=2000,000,000),表示难度序列。
输出
输出:最大的字串长度。
样例输入
3 9
5 1 3 5 8 6 6 9 10
样例输出
4
题解
双指针法+STL-set
考虑随着做端点向右移动,右端点的选择是单调不降的。所以可以使用双指针法扫出以某个点为左端点的最长的区间。
此时需要维护区间最值,可以使用单调队列来在线性时间内解决。当然本题也可以像我一样使用set水过。
#include <cstdio>
#include <set>
using namespace std;
multiset<int> s;
int a[3000010];
int main()
{
int k , n , i , p , ans = 0;
scanf("%d%d" , &k , &n);
for(i = 1 ; i <= n ; i ++ ) scanf("%d" , &a[i]);
for(i = p = 1 ; i <= n ; i ++ )
{
while(p <= n && (s.empty() || max(*(--s.end()) , a[p]) - min(*s.begin() , a[p]) <= k)) s.insert(a[p ++ ]);
ans = max(ans , p - i) , s.erase(s.find(a[i]));
}
printf("%d\n" , ans);
return 0;
}
最新文章
- [实战]MVC5+EF6+MySql企业网盘实战(29)——更新日志
- 如何识别一个字符串是否Json格式
- Struts2文件下载找不到输入流异常
- jQuery实现等比例缩放大图片
- Hibernate API申明事务边界
- C++ string的常用功能
- 为Delphi程序增加UAC功能(管理员身份运行exe)
- python学习之列表
- Lucene打分规则与Similarity模块详解
- Django Web开发【6】使用Ajax增强用户体验
- 在graphviz中创建可点击的图形
- selenium + python自动化测试(一)
- react native 开发报错
- Kafka命令清单
- Linux kernel Programming - Concurrency and Race Conditions
- NumPy 迭代数组
- Redis-五种数据类型解析
- Popupwindow全屏问题
- 无法安装Java,以下开关中存在错误:“0”
- httpd:RSA certificate configured for SERVER does NOT include an ID which matches the server name