Skip to content

「USACO 2012 March (Silver)」Flowerpot

检测到 KaTeX 加载失败,可能会导致文中的数学公式无法正常渲染。

#题面

#题目描述

Farmer John has been having trouble making his plants grow, and needs your help to water them properly. You are given the locations of NN raindrops (1N1051 \leq N \leq 10^5) in the 2D plane, where yy represents vertical height of the drop, and xx represents its location over a 1D number line:

Each drop falls downward (towards the xx-axis) at a rate of 11 unit per second. You would like to place Farmer John’s flowerpot of width WW somewhere along the xx axis so that the difference in time between the first raindrop to hit the flowerpot and the last raindrop to hit the flowerpot is at least some amount DD (so that the flowers in the pot receive plenty of water). A drop of water that lands just on the edge of the flowerpot counts as hitting the flowerpot.

Given the value of DD and the locations of the NN raindrops, please compute the minimum possible value of WW.

#输入格式

  • Line 11: Two space-separated integers, NN and DD. (1D1061 \leq D \leq 10^6)
  • Lines 2N+12 \sim N + 1: Line i+1i + 1 contains the space-separated (x,y)(x, y) coordinates of raindrop ii, each value in the range [0,106][0, 10^6].

#输出格式

  • Line 11: A single integer, giving the minimum possible width of the flowerpot. Output 1-1 if it is not possible to build a flowerpot wide enough to capture rain for at least DD units of time.

#输入输出样例

样例输入 #1

4 5
6 3
2 4
4 10
12 15

样例输出 #1

2

样例解释 #1

There are 44 raindrops, at (6,3)(6, 3), (2,4)(2, 4), (4,10)(4, 10), and (12,15)(12, 15). Rain must fall on the flowerpot for at least 55 units of time.

A flowerpot of width 22 is necessary and sufficient, since if we place it from x=46x = 4 \dots 6, then it captures raindrops 11 and 33, for a total rain duration of 103=710-3 = 7.

#思路

考场上想出来的做法,题解里好像没有一样的思路。

本题需要注意的点是,第一滴水和最后一滴水之间间隔的时间不一定恰好为 DD,而是 D\geq D,一定要看清楚题,场上因为这个浪费了一个小时的时间。

将所有点按 yy 值排序之后,开一个 set 记录 yjyidy_j \leq y_i - d 的对应的 xjx_j 值。因为题目中没有对第一滴水和最后一滴水之间接水数量之间做要求,所以直接在 set 中查询 xix_i 的前驱和后继,取两个方向上长度的最小值更新答案即可。

#代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <iostream>
#include <algorithm>
#include <cmath>
#include <limits>
#include <set>
#include <utility>

using std::cin;
using std::cout;
const char endl = '\n';

const int N = 1e5 + 5;

int n, d, ans = std::numeric_limits<int>::max();
std::pair<int, int> points[N];
std::set<int> set;

int main() {
std::ios::sync_with_stdio(false);
cin.tie(nullptr);

cin >> n >> d;

for (int i = 1; i <= n; i++) {
cin >> points[i].first >> points[i].second;
}

std::sort(points + 1, points + 1 + n, [](auto a, auto b) -> bool {
return a.second < b.second;
});

int lst = 1;
for (int i = 1; i <= n; i++) {
int pos = std::upper_bound(
points + 1,
points + 1 + n,
std::make_pair(0, points[i].second - d),
[](auto a, auto b) -> bool {
return a.second < b.second;
})
- points;

for (int j = lst; j < pos; j++) {
set.insert(points[j].first);
}

lst = pos;

auto it1 = set.lower_bound(points[i].first),
it2 = set.upper_bound(points[i].first);

if (it1 != set.begin()) {
ans = std::min(ans, std::abs(points[i].first - *--it1));
}

if (it2 != set.end()) {
ans = std::min(ans, std::abs(points[i].first - *it2));
}
}

cout << (ans == std::numeric_limits<int>::max() ? -1 : ans) << endl;

return 0;
}