[USACO12MAR]花盆 二分 单调队列

[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;
}
上一篇:NOIP模拟 最佳序列 - 二分 + 单调队列


下一篇:[BZOJ1044][HAOI2008]木棍分割 二分 + 单调队列优化dp + 滚动数组优化dp