P2698 [USACO12MAR]花盆Flowerpot

題目描述

Farmer John has been having trouble making his plants grow, and needs your help to water them properly. You are given the locations of N raindrops (1 <= N <= 100,000) in the 2D plane, where y represents vertical height of the drop, and x represents its location over a 1D number line:

Each drop falls downward (towards the x axis) at a rate of 1 unit per second. You would like to place Farmer John's flowerpot of width W somewhere along the x 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 D (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 D and the locations of the N raindrops, please compute the minimum possible value of W.

老板需要你幫忙澆花。給出N滴水的坐標，y表示水滴的高度，x表示它下落到x軸的位置。

每滴水以每秒1個單位長度的速度下落。你需要把花盆放在x軸上的某個位置，使得從被花盆接著的第1滴水開始，到被花盆接著的最后1滴水結束，之間的時間差至少為D。

我們認為，只要水滴落到x軸上，與花盆的邊沿對齊，就認為被接住。給出N滴水的坐標和D的大小，請算出最小的花盆的寬度W。

輸入輸出格式

輸入格式：

第一行2個整數 N 和 D。

第2.. N+1行每行2個整數，表示水滴的坐標(x,y)。

輸出格式：

僅一行1個整數，表示最小的花盆的寬度。如果無法構造出足夠寬的花盆，使得在D單位的時間接住滿足要求的水滴，則輸出-1。

輸入輸出樣例

輸入樣例#1：?
4 5 6 3 2 4 4 10 12 15 輸出樣例#1：?
2

說明

【樣例解釋】

有4滴水， (6,3), (2,4), (4,10), (12,15).水滴必須用至少5秒時間落入花盆。花盆的寬度為2是必須且足夠的。把花盆放在x=4..6的位置，它可以接到1和3水滴, 之間的時間差為10-3 = 7滿足條件。

【數據范圍】

40%的數據：1 ≤ N ≤ 1000，1 ≤ D ≤ 2000；

100%的數據：1 ≤ N ≤ 100000，1 ≤ D ≤ 1000000，0≤x,y≤10^6。

?

sol：單調隊列蠻顯然的吧（其實接近板子題）

維護一個遞增的單調隊列，當隊尾與隊首的高度差>D時彈隊首，當隊尾比當前元素大時彈隊尾

#include <bits/stdc++.h> using namespace std; typedef long long ll; inline ll read() {ll s=0;bool f=0;char ch=' ';while(!isdigit(ch)){f|=(ch=='-'); ch=getchar();}while(isdigit(ch)){s=(s<<3)+(s<<1)+(ch^48); ch=getchar();}return (f)?(-s):(s); } #define R(x) x=read() inline void write(ll x) {if(x<0){putchar('-'); x=-x;}if(x<10){putchar(x+'0'); return;}write(x/10);putchar((x%10)+'0');return; } #define W(x) write(x),putchar(' ') #define Wl(x) write(x),putchar('\n') const int N=100005,inf=0x3f3f3f3f; int n,D; struct Shuidi {ll X,Y; }Water[N]; inline bool cmp(Shuidi p,Shuidi q) {return p.X<q.X; } struct Record {ll Weiz,Shuz; }Ddq[N]; int main() {int i,j;R(n); R(D);for(i=1;i<=n;i++){int x=read(),y=read();Water[i]=(Shuidi){x,y};}sort(Water+1,Water+n+1,cmp);int Head=1,Tail=0;ll ans=inf;for(i=1;i<=n;i++){while(Head<Tail&&Water[Ddq[Head+1].Weiz].Y+D<=Water[Ddq[Tail].Weiz].Y) Head++;if(Water[Ddq[Head].Weiz].Y+D<=Water[Ddq[Tail].Weiz].Y) ans=min(ans,Ddq[Tail].Shuz-Ddq[Head].Shuz);while(Head<=Tail&&Water[Ddq[Tail].Weiz].Y>Water[i].Y) Tail--;Ddq[++Tail]=(Record){i,Water[i].X};}if(ans==inf) puts("-1");else Wl(ans);return 0; } /* input 4 5 6 3 2 4 4 10 12 15 output 2 */ View Code

?

轉載于:https://www.cnblogs.com/gaojunonly1/p/10579836.html

總結

以上是生活随笔為你收集整理的洛谷P2698 [USACO12MAR]花盆Flowerpot的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。