【bzoj2096】[Poi2010]Pilots 双指针法+STL-set
set 指针 STL
2023-09-11 14:22:40 时间
题目描述
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; }
相关文章
- ELASTICSEARCH7.4 免费启用X-PACK插件 设置账号、权限 包含错误--ERROR: FAILED TO SET PASSWORD FOR USER [APM_SYSTEM]
- 第十九节,基本数据类型,集合set
- [Javascript] Filter out Duplicates from Flat JavaScript Array with array.filter / reduce / Set
- [Javascript] Broadcaster + Operator + Listener pattern -- 10. Define a Function to Set Common Behaviors in Operators
- LeetCode-819. 最常见的单词【map,unordered_set,】
- java中List、Array、Map、Set等集合相互转换的最佳方法
- Object reference not set to an instance of an object.
- SAP CRM中间件Generic stop set的错误如何解决
- BCset BC set how entry is inserted to Database table when activated
- Chrome开发者工具Network标签页中观察到的set-cookie jsessionid是什么东西
- Python之pandas:pandas.set_option函数的参数详细解释
- Java类集-set
- leetcode 645. Set Mismatch——凡是要节约空间的题目 都在输入数据上下功夫 不要担心破坏原始的input
- Mybatis set标签
- 一种是CI(Constructor Injection)构造方法注入,另一种是SI(Set Injection) set 注入
- 【Python 3】Set集合的解析与使用
- Could not load org.apache.hadoop.hive.conf.HiveConf. Make sure HIVE_CONF_DIR is set correctly.