P2698 [USACO12MAR] Flowerpot S
monotonic queue, https://www.luogu.com.cn/problem/P2698
思路：双指针+单调队列
cpp
#include <bits/stdc++.h>
using namespace std;
int n, D;
const int N = 1e5+20;
pair<int, int> r[N];
pair<int, int> ql[N], qr[N];
int qlh, qlt, qrh, qrt;
int main() {
unsigned W = -1;
cin >> n >> D;
for (int i=0; i<n; i++)
cin >> r[i].first >> r[i].second;
sort(r, r+n);
qlh = qlt = qrh = qrt = 0;
for (int i=0, j=0; i<n; i++) {
if (qlh != qlt and ql[qlh].first < i) qlh++;
if (qrh != qrt and qr[qrh].first < i) qrh++;
while (j<n and ql[qlh].second-qr[qrh].second < D) {
int y = r[j].second; // j, y
while (qlh != qlt and ql[qlt-1].second <= y) {
qlt--;
}
ql[qlt] = make_pair(j, y); qlt++;
while (qrh != qrt and qr[qrt-1].second >= y) {
qrt--;
}
qr[qrt] = make_pair(j, y); qrt++;
j++;
}
if (ql[qlh].second-qr[qrh].second >= D) {
//cout << i << ' ' << j << endl;
W = min(W, unsigned(r[j-1].first-r[i].first));
}
}
cout << int(W) << endl;
return 0;
}思路：一眼顶针鉴定为二分答案。然后用 rust 写了下试试
rust
// use std::collections::VecDeque;
// use std::fs::read;
use std::{
collections::VecDeque,
io::{self, BufWriter, Read, Write},
};
struct FastReader<R: Read> {
reader: R,
buffer: [u8; 65536],
pos: usize,
cap: usize,
}
impl<R: Read> FastReader<R> {
fn new(reader: R) -> Self {
Self {
reader,
buffer: [0; 65536],
pos: 0,
cap: 0,
}
}
fn read_byte(&mut self) -> Option<u8> {
if self.pos >= self.cap {
self.cap = self.reader.read(&mut self.buffer).ok()?;
self.pos = 0;
if self.cap == 0 {
return None;
}
}
let b = self.buffer[self.pos];
self.pos += 1;
Some(b)
}
fn next_int<T: FromIntegral>(&mut self) -> T {
let mut b = self.read_byte().unwrap();
while b <= b' ' {
b = self.read_byte().unwrap();
}
let mut neg = false;
if b == b'-' {
neg = true;
b = self.read_byte().unwrap();
}
let mut res = T::from_u8(b - b'0');
while let Some(c) = self.read_byte() {
if c <= b' ' {
break;
}
res = res * T::from_u8(10) + T::from_u8(c - b'0');
}
if neg { T::zero() - res } else { res }
}
fn next_string(&mut self) -> String {
let mut b = self.read_byte().unwrap();
while b <= b' ' {
b = self.read_byte().unwrap();
}
let mut res = String::new();
res.push(b as char);
while let Some(c) = self.read_byte() {
if c <= b' ' {
break;
}
res.push(c as char);
}
res
}
}
trait FromIntegral:
std::ops::Mul<Output = Self> + std::ops::Add<Output = Self> + std::ops::Sub<Output = Self> + Copy
{
fn from_u8(v: u8) -> Self;
fn zero() -> Self;
}
macro_rules! impl_integral {
($($t:ty)*) => { $( impl FromIntegral for $t {
fn from_u8(v: u8) -> Self { v as $t }
fn zero() -> Self { 0 }
} )* };
}
impl_integral!(i32 i64 isize usize i128 u8 u16 u32 u64 u128);
type Point = (i32, i32);
fn check(x: i32, a: &[Point], d: i32, q_min: &mut [usize], q_max: &mut [usize]) -> bool {
let mut head_min = 0;
let mut tail_min = 0;
let mut head_max = 0;
let mut tail_max = 0;
let mut l = 0;
for r in 0..a.len() {
while tail_min > head_min && a[q_min[tail_min - 1]].1 >= a[r].1 {
tail_min -= 1;
}
q_min[tail_min] = r;
tail_min += 1;
while tail_max > head_max && a[q_max[tail_max - 1]].1 <= a[r].1 {
tail_max -= 1;
}
q_max[tail_max] = r;
tail_max += 1;
while a[r].0 - a[l].0 > x {
l += 1;
if q_min[head_min] < l {
head_min += 1;
}
if q_max[head_max] < l {
head_max += 1;
}
}
if a[q_max[head_max]].1 - a[q_min[head_min]].1 >= d {
return true;
}
}
false
}
fn main() {
let mut reader = FastReader::new(io::stdin().lock());
let mut writer = BufWriter::new(io::stdout().lock());
let n: usize = reader.next_int();
let d: i32 = reader.next_int();
let mut a: Vec<Point> = Vec::with_capacity(n);
for _ in 0..n {
a.push((reader.next_int(), reader.next_int()));
}
a.sort_unstable_by_key(|p| p.0);
let mut q_min = vec![0; n];
let mut q_max = vec![0; n];
let mut l = 0;
let mut r = 1000001;
let mut ans = -1;
while l <= r {
let mid = (l + r) >> 1;
if check(mid, &a, d, &mut q_min, &mut q_max) {
ans = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
writeln!(writer, "{}", ans).unwrap();
}思路：按 x 排序，对于每个 (x,y) 为左端点，找到最靠左的右端点满足 y 坐标之差大于等于 d，单调队列实现。
方法二：按 y 排序，找到符合要求的点钟与当前 (x,y) 横坐标差的绝对值最小的，平衡树实现（实则用 STL::set逃课）
代码
python
n,d = map(int,input().split())
a = []
for i in range(n):
a.append(tuple(map(int,input().split())))
b = sorted(a,key = lambda x: x[0])
d1,d2 = [0]*n,[0]*n
h1,h2,t1,t2 = 0,0,-1,-1
inf = 2e9
ans = inf
r = -1
for l in range(n):
while(h1<=t1 and d1[h1]<l): h1 += 1
while(h2<=t2 and d2[h2]<l): h2 += 1
while(r<n-1 and b[d1[h1]][1]-b[d2[h2]][1]<d):
r += 1
while(h1<=t1 and b[d1[t1]][1]<=b[r][1]): t1 -= 1
while(h2<=t2 and b[d2[t2]][1]>=b[r][1]): t2 -= 1
t1 += 1
t2 += 1
d1[t1] = r
d2[t2] = r
# print(l,r)
if(r!=n-1):
ans = min(ans,b[r][0]-b[l][0])
if(ans>=inf):
print(-1)
else:
print(ans)方法二：
cpp
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define For(i,l,r) for(ll i=(l),i##_=(r);i<=i##_;++i)
#define FOR(i,l,r) for(ll i=(l),i##_=(r);i>=i##_;--i)
#define Rep(i,l,r) for(ll i=(l),i##_=(r);i<i##_;++i)
#define pr pair<ll,ll>
pr a[100010];
const ll inf = 1e9;
set<ll> s;
int main(){
ll n,d;cin>>n>>d;
For(i,1,n){
ll x,y;cin>>x>>y;
a[i] = make_pair(x,y);
}
sort(a+1,a+n+1,[](pr a,pr b){return a.second<b.second;});
ll r = n,ans = inf;
FOR(l,n,1){
// if(a[r].second-a[l].second<d) continue;
while(a[r].second-a[l].second>=d)
s.insert(a[r].first),--r;
auto it = s.lower_bound(a[l].first);
ll x1=-inf*2,x2=inf*2;
if(it!=s.end()) x2 = *it;
if(it!=s.begin()) --it,x1 = *it;
ans = min(ans,min(x2-a[l].first,a[l].first-x1));
}
cout<<(ans>=inf?-1ll:ans);
return 0;
}