[USACO12MAR]花盆 二分 单调队列
2024-09-08 06:58:41
[USACO12MAR]花盆 二分 单调队列
存在一个长度为\(x\)的区间\([l,r]\),使得区间中最大值与最小值差至少为\(w\),求这个最小的\(x\)
\(n\le 100000\),\(w\le 1000000\)
显然区间长度\(x\)越大,最值之差越大,满足单调性,上二分答案,问题转化为是否存在长度为\(mid\)的区间中最值之差至少为\(w\),而这个问题可以用单调队列(滑动窗口)\(O(n)\)解决。
单调队列存的下标,首先判断队首是否合法(窗口大小),然后按照“比你强还比你年轻”的原则弹队尾维护队列即可。
#include <cstdio>
#include <algorithm>
#define MAXN 100010
using namespace std;
int n,d;
struct nod{
int x,y;
const bool operator < (const nod &a) const{
return x<a.x;
}
} a[MAXN];
namespace quemx {
int q[MAXN],head,tail;
}
namespace quemin {
int q[MAXN],head,tail;
}
inline bool check(int wid) {
quemx::head=1,quemx::tail=0;
quemin::head=1,quemin::tail=0;
for(int i=1;i<=n;++i){
// 滑动窗口宽度
while(quemx::head<=quemx::tail&&a[i].x-a[quemx::q[quemx::head]].x>wid) ++quemx::head;
while(quemin::head<=quemin::tail&&a[i].x-a[quemin::q[quemin::head]].x>wid) ++quemin::head;
// 维护单调队列
while(quemx::head<=quemx::tail&&a[quemx::q[quemx::tail]].y<=a[i].y) --quemx::tail;
while(quemin::head<=quemin::tail&&a[quemin::q[quemin::tail]].y>=a[i].y) --quemin::tail;
// 入队
quemx::q[++quemx::tail]=i;
quemin::q[++quemin::tail]=i;
if(a[quemx::q[quemx::head]].y-a[quemin::q[quemin::head]].y>=d) return 1;
}
return 0;
}
int main() {
scanf("%d %d", &n, &d);
int l=1,r=0;
for(int i=1;i<=n;++i) scanf("%d%d", &a[i].x, &a[i].y), r=max(r, a[i].x);
sort(a+1, a+1+n);
int ans=-1;
while(l<=r){
int mid=(l+r)>>1;
if(check(mid)) r=mid-1, ans=mid;
else l=mid+1;
}
printf("%d\n", ans);
return 0;
}
最新文章
- javascript的继承小结
- Windows转到linux中,文件乱码,文件编码转换 &; 解决sqlplus连接oracle乱码
- Android性能优化系列 + Android官方培训课程中文版
- 記錄一次CRS-0184: Cannot communicate with the CRS daemon的解決
- 如何开启SQL Server 2008的远程联机
- 企业高并发的成熟解决方案(一)video(笔记&;知识点)
- Mysql技术内幕-笔记-第二章 数据类型
- DotNet程序汉化过程--SnippetCompiler简单解说
- [Android学习笔记]try-catch
- git 配置SSH免密
- struts2 之 struts2数据校验
- Mysql索引介绍及常见索引的区别
- Python数据预处理:机器学习、人工智能通用技术(1)
- 印象笔记无法连服务器(internet explore的问题)
- POJ 1177Picture 扫描线(若干矩形叠加后周长)
- sap 下载程序
- Nginx下配置ThinkPhp多入口访问
- Maven如何发布项目到一个Tomcat中
- 1.Hadoop集群搭建之Linux主机环境准备
- SparkSQL之更改表结构
热门文章
- 【题解】Luogu P5360 [SDOI2019]世界地图
- java中四种权限修饰符区别
- mysql-多表联查(实例)
- Python进阶(九)----json模块, pickle模块, os模块,sys模块,hashlib模块
- 原生JavaScript实现轮播图
- PL/SQL的结构
- webpack练手项目之easySlide(一):初探webpack
- Requirements management in confluence
- AIX安装单实例11gR2 GRID+DB
- maven学习笔记二(了解maven的基本命令)