題意：

給出N滴水的坐標，y表示水滴的高度，x表示它下落到x軸的位置。

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

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

?

數據范圍：

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

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

--------------------------------------------------我是分割線----------------------------------------------------

題解：對于40%的數據，二分花盆的寬度，樸素O（N^2）檢驗寬度len能否滿足條件，總時間復雜度O（N^2logN），期望得分40，實際得分50。

#include<bits/stdc++.h>#define ll long long #define mp make_pair #define rep(i, a, b) for(int i = (a); i <= (b); i++) #define per(i, a, b) for(int i = (a); i >= (b); i--)using namespace std;typedef pair<int, int> pii; typedef double db; const int N = 1e6 + 50; struct node{ int x, y; } a[N]; int n, d, l = 1, r, ans = -1; inline int read(){int x = 0, f = 1;char ch = getchar();while(ch < '0' || ch > '9') { if(ch == '-') f = -1; ch = getchar();}while(ch >='0' && ch <='9') { x = (x<<3)+(x<<1)+(ch^48); ch = getchar();}return x*f; } bool mycmp(node a, node b){ return a.x < b.x; } void init(){n = read(); d = read();rep(i, 1, n) a[i].x = read(), a[i].y = read(), r = max(r, a[i].x);sort(a+1, a+n+1, mycmp); } bool check(int len){int dist = 0;rep(i, 1, n){int t = a[i].y, maxx = 0;maxx = max(maxx, a[i].y);rep(j, i+1, n){if(i == j) continue;if(a[j].x >= a[i].x && a[j].x <= a[i].x + len) {maxx = max(maxx, a[j].y);t = min(t, a[i].y);}}dist = max(dist, abs(maxx - t)); if(dist >= d) return true;}return false; } void work(){while(l < r){int mid = (l+r) >> 1;if(check(mid)) r = mid, ans = mid;else l = mid + 1;}printf("%d\n", ans); } int main(){init();work();return 0; } View Code

考慮對樸素算法進行優化，我們發現，檢驗的過程max-min的值我們可以預處理維護的，于是把整條x軸看成一個區間，每個水滴的y值看成是區間下標的權值，于是我們就不難想到ST表，運用ST表預處理區間的最大值和最小值，于是可以O（N）檢驗。總時間復雜度O（NlogN），常數略大。

#include<bits/stdc++.h>#define ll long long #define mp make_pair #define rep(i, a, b) for(int i = (a); i <= (b); i++) #define per(i, a, b) for(int i = (a); i >= (b); i--)using namespace std;typedef pair<int, int> pii; typedef double db; const int N = 1e5 + 50; struct node{ int x, y; } a[N]; int n, d, l = 1, r, ans = -1, maxn; int Max[N*10][21], Min[N*10][21]; inline int read(){int x = 0, f = 1;char ch = getchar();while(ch < '0' || ch > '9') { if(ch == '-') f = -1; ch = getchar();}while(ch >='0' && ch <='9') { x = (x<<3)+(x<<1)+(ch^48); ch = getchar();}return x*f; } int ask_max(int l, int r){int k = log2(r-l+1);return max(Max[l][k], Max[r - (1<<k) + 1][k]); } int ask_min(int l, int r){int k = log2(r-l+1);return min(Min[l][k], Min[r - (1<<k) + 1][k]); } void init(){memset(Min, 0x3f, sizeof(Min));n = read(); d = read();rep(i, 1, n){a[i].x = read(), a[i].y = read(), maxn = max(maxn, a[i].x);Max[a[i].x][0] = max(Max[a[i].x][0], a[i].y);Min[a[i].x][0] = min(Min[a[i].x][0], a[i].y);}int t = log2(maxn);rep(j, 1, t) rep(i, 1, maxn - (1<<j) + 1) {Max[i][j] = max(Max[i][j-1], Max[i + (1<<(j-1))][j-1]); Min[i][j] = min(Min[i][j-1], Min[i + (1<<(j-1))][j-1]);} } bool check(int len){rep(i, 1, maxn-len){if(ask_max(i, i+len) - ask_min(i, i+len) >= d) return true;}return false; } void work(){r = maxn;while(l <= r){int mid = (l+r) >> 1;if(check(mid)) r = mid-1, ans = mid;else l = mid + 1;}printf("%d\n", ans); } int main(){init();work();return 0; } View Code

這里再介紹一種新的維護方法，即動態維護區間最大值和最小值的基本套路。

當我們二分到一個長度時，對于這個長度所能產生的最大的貢獻即為max{max[i，i+len] - min[i，i+len] }。

這時，我們就可以使用單調隊列。

維護兩個單調隊列，分別是單調不降和單調不升的隊列，兩個隊頭{min，max}即為所需求的答案。

至于怎么維護，維護單調隊列的基本形式，如果隊頭沒有下一個元素優，那么就彈出隊頭，直到符合單調性為止，然后對隊尾操作，使得隊列包含的區間長度等于len+1。

總時間復雜度O（NlogN），常數較小。

#include<bits/stdc++.h>#define ll long long #define mp make_pair #define rep(i, a, b) for(int i = (a); i <= (b); i++) #define per(i, a, b) for(int i = (a); i >= (b); i--)using namespace std;typedef pair<int, int> pii; typedef double db; const int N = 1e6 + 50; struct node{ int x, y; } a[N]; int n, d, maxx, ans = -1, b[N], k[N]; struct npp{ int z, id; } ql[N], qh[N]; inline int read(){int x = 0, f = 1;char ch = getchar();while(ch < '0' || ch > '9') { if(ch == '-') f = -1; ch = getchar();}while(ch >='0' && ch <='9') { x = (x<<3)+(x<<1)+(ch^48); ch = getchar();}return x*f; } void init(){memset(k, 0x3f, sizeof(k));n = read(); d = read();rep(i, 1, n) a[i].x = read(), a[i].y = read(), maxx = max(maxx, a[i].x);rep(i, 1, n) b[a[i].x] = max(b[a[i].x], a[i].y); rep(i, 1, n) k[a[i].x] = min(k[a[i].x], a[i].y); } bool check(int len){len++;int ls = 1, rs = 0, lh = 1, rh = 0, sum = 0;rep(i, 1, maxx) {while(ls <= rs && k[i] <= ql[rs].z) rs--;while(lh <= rh && b[i] >= qh[rh].z) rh--;while(ql[ls].id <= i-len) ls++;while(qh[lh].id <= i-len) lh++;ql[++rs].z = k[i], ql[rs].id = i;qh[++rh].z = b[i], qh[rh].id = i;if(i >= len) sum = max(sum, qh[lh].z - ql[ls].z);if(sum >= d) return true;} return false; } void work(){int l = 1, r = maxx;while(l <= r){int mid = (l+r) >> 1;if(check(mid)) r = mid-1, ans = mid;else l = mid+1;}printf("%d\n", ans); } int main(){init();work();return 0; } View Code

?其實除了單調隊列以外，動態維護區間最值還可以用STL的<set>，或者堆，不過時間復雜度要多一個log，可能會被卡常，推薦使用單調隊列。

轉載于:https://www.cnblogs.com/smilke/p/11572809.html

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的[USACO12MAR]花盆Flowerpot 二分答案+单调队列的全部內容，希望文章能夠幫你解決所遇到的問題。

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