【HDU5289】Assignment
2024-09-05 18:43:28
题目大意:给定一个长度为 N 的序列,求序列中最大值和最小值相差小于 K 的连续段的个数。
题解:
最大值和最小值相差不超过 K 是一个在值域角度的限制,应考虑采用平衡树或权值...数据结构进行维护。
连续的一段即可考虑采用双指针进行维护即可。
注意:
- r 是当前需要判断的情况,故 r 从 1 开始。
代码如下
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
typedef long long LL;
int n,k,a[maxn];
multiset<int> s;
void read_and_parse(){
s.clear();
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
}
bool right(int val){
if(s.empty())return 1;
else return abs(*s.begin()-val)<k&&abs(*--s.end()-val)<k;
}
void solve(){
LL ans=0;
for(int l=1,r=1;l<=n;l++){
while(r<=n&&right(a[r]))s.insert(a[r++]);
ans+=r-l;
s.erase(s.find(a[l]));
}
printf("%lld\n",ans);
}
int main(){
int T;scanf("%d",&T);
while(T--){
read_and_parse();
solve();
}
return 0;
}
最新文章
- OAuth2.0相关知识
- 使用supervisor监控进程
- 免费微信公众号专用h5在线电影票API
- 整理的一些常用的CSS HACK
- tablet 的使用
- python 笔记(一)
- ASP.NET问题处理---“数据请求超时错误“”
- 页面全屏显示JS代码
- Ubuntu14.04搭建安装svnserver
- Unity3D移植到自己的Android程序
- java的控制流程
- 继承Application实现Android数据共享
- mysql解决中文乱码问题
- vue手把手教你实现走马灯商品左右轮播图
- SQL注入--SQLMap过WAF
- nagios 监控内存使用情况
- layui模板和jfinal混合使用注意
- Android Studio 编译错误
- node 随便升级到最新版本的遭遇
- Eclipse中让Scala缩进变为4
热门文章
- Selenium 2自动化测试实战10(鼠标事件)
- oracle审计登录失败用户
- java:常用类(包装类,equals和==的比较,Date,java.lang.String中常用方法,枚举enum)
- ubuntu分区建议总结
- vue-cli 3 ----- 项目频繁发送‘sockjs-node/info’请求
- IDEA github 上传项目, 拉取, 删除
- Akka系列(十):Akka集群之Akka Cluster
- Mac OS X 11中的/usr/bin 的“Operation not permitted”
- Yarn-本地获取任务日志
- etcd集群移除节点