第3次训练的H题解

题目：[USACO 2012 Mar S]Flowerpo

题目大意：给定N个雨滴的位置（1 <= N <= 100,000），每个雨滴在二维平面上落下，其中y表示雨滴的垂直高度，x表示其在一维数轴上的位置。每个雨滴以每秒1个单位的速度向下落（朝向x轴）。现在需要在x轴上放置一个宽度为W的花盆，使得第一个落在花盆里的雨滴和最后一个落在花盆里的雨滴之间的时间差至少为D（以便花盆里的植物能够得到充足的水分）。如果一个水滴恰好落在花盆的边缘上，则计为落在花盆内。给定D和N个雨滴的位置，请计算W的最小可能值。

话说看到最大最小，我的第一印象就是二分了

训魔怔了（）

由于落下的雨滴速度匀速且速度为1（反现实雨滴）那么高度就是落下的时间

首先我们先按雨滴给的x轴进行排序，至于接雨滴部分，其实我们只要花盆里最先落下的雨滴和最晚落下的雨滴就可以啦，维护一个固定长度，会移动的区间，我们可以很自然的想到滑动窗口，但由于给的专题训练是队列，（话说单调队列不也是队列，不是），那么我们就可以用堆去快速的找最大最小值 （决不是想偷懒）

那么在存的时候就是要存两个东西了，雨滴落下的时间以及雨滴x坐标

第一部分 二分板

int l = 1 , r = 1e6;
	while(l < r){
		int mid = (l + r) >> 1;
		if(check(mid)) r = mid;
		else  l = mid + 1;
		//cout << l << " "   << r << "\n";
	}
	if(l >= 1e6) cout << -1 << "\n";
	else cout << l  << "\n";

第二部分

bool check(int x){
	priority_queue<pair<int ,int > , vector<pair<int , int >>,greater<pair<int , int >>> q;
	priority_queue<pair<int ,int > ,vector<pair<int , int >> ,less<pair<int , int >>> p;
	for(int i =  1 ; i <= n ; i ++){
		p.push({a[i].second,a[i].first});
		q.push({a[i].second,a[i].first});
		while(!p.empty() && p.top().second + x < a[i].first  ) p.pop();
		while(!q.empty() && q.top().second + x < a[i].first  ) q.pop();
		if(!q.empty() && p.top().first - q.top().first >= d) return true;
	}
	return false;
}

那么我们就好好看一下check部分 ，首先先开一个大根堆和小根堆，毕竟要找最大和最小， 其实滑动窗口的左边界不就是雨滴的x坐标吗，那么一开始我们这个滑动窗口的覆盖范围不就是a[i].first 到 a[i].first + x 吗

		while(!p.empty() && p.top().second + x < a[i].first  ) p.pop();
		while(!q.empty() && q.top().second + x < a[i].first  ) q.pop();

这两部分不就是模拟滑动窗口元素弹出，建议结合滑动窗口理解

完成ac代码就是

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm> 
using namespace std;
const int N = 1e5 + 10;
pair<int ,int >a[N];
int n , d;
bool check(int x){
	priority_queue<pair<int ,int > , vector<pair<int , int >>,greater<pair<int , int >>> q;
	priority_queue<pair<int ,int > ,vector<pair<int , int >> ,less<pair<int , int >>> p;
	for(int i =  1 ; i <= n ; i ++){
		p.push({a[i].second,a[i].first});
		q.push({a[i].second,a[i].first});
		while(!p.empty() && p.top().second + x < a[i].first  ) p.pop();
		while(!q.empty() && q.top().second + x < a[i].first  ) q.pop();
		if(!q.empty() && p.top().first - q.top().first >= d) return true;
	}
	return false;
}
int main(){
	
	cin >> n >> d;
	
	for(int i = 1 ; i <= n ; i ++){
		cin >> a[i].first >> a[i].second;
	}
	sort(a + 1 , a + 1 + n);
	int l = 1 , r = 1e6;
	while(l < r){
		int mid = (l + r) >> 1;
		if(check(mid)) r = mid;
		else  l = mid + 1;
		//cout << l << " "   << r << "\n";
	}
	if(l >= 1e6) cout << -1 << "\n";
	else cout << l  << "\n";
}