目錄

• @description@
• @solution@
• @accepted code@
• @details@

---

@description@

小Q計劃在自己的新家中購置一臺圓形的掃地機器人。小Q的家中有一個寬度為 m 的走廊，走廊很長，如果將這個走廊的俯視圖畫在平面直角坐標系上的話，那么走廊的兩堵墻可以分別看作直線 y=0 和直線 y=m，兩堵墻之間的部分代表走廊。

小Q會按照順序依次在走廊中安置 n 個家具。第 i 個家具的位置為 (xi,yi)，寬度可以忽略不計，同一個位置可能會有多個家具。

在商店中，掃地機器人的半徑只能是整數。請找到最大可能的整數半徑 R，使得以 R 為半徑的掃地機器人可以從走廊的最左側到達最右側，掃地機器人不可以穿過家具或者墻壁，但是允許接觸它們。

請寫一個程序，幫助小 Q 在每次安置下新的家具后，都能計算出這個條件下允許通過的掃地機器人的最大可能半徑。

input
第一行包含兩個正整數 n, m，分別表示家具的數量和走廊的寬度。

接下來 n 行，每行兩個正整數 xi, yi，表示第 i 個被安置下的家具的位置。

output
輸出 n 行，每行輸出一個整數，第 i 行輸出在安置下前 i 個家具后，掃地機器人的半徑的最大可能值。

sample input
5 6
1 2
3 2
2 1
1 3
4 5
sample output
2
2
2
1
1

對于 100% 的數據：1≤xi≤10^9，1≤yi<m≤10^9，n≤2500。

@solution@

不妨看看給定機器人半徑為 r0 的情況下會發生什么。

我們可以以障礙為圓心，畫出一個半徑為 r0 的禁行區域（即：機器人的圓心不能經過這個區域）。
同時也可以以兩面墻畫出相應的禁行區域。
此時如果禁行區域將兩面墻連接在一起，該半徑 r0 不合法。

稍微轉換一下：
如果半徑 x 是使得障礙/墻 a, b 所對應的禁行區域連接（即有交集）的最小整數半徑，我們就在 a, b 之間連一條邊權為 x 的邊。
當半徑為 r0 的時候，如果存在一條兩面墻之間的路徑，使得路徑上的每一條邊的邊權 <= r0，則 r0 不合法。
等價于路徑上的最大邊權 <= r0。

題目要求的是最大合法的整數半徑 R，但我們可以將問題做一個簡單的轉換：找到最小合法的整數半徑 R'。
因為是整數，所以可以得到 R = R' - 1。

問題最終可以轉換為：找到兩墻之間的一條路徑，使這條路徑上的最大值最小。
這是一個典型的最小生成樹應用。

怎么動態維護最小生成樹呢？
一開始我原本想的是用 lct 來搞，看了題解才發現：

woc 它只需要求 O(n) 次最小生成樹，所以沒必要每個時刻的最小生成樹都求解出來。
于是：每次加入一個新的障礙，增加 O(n) 條邊，與上個時刻的最小生成樹一起（也是 O(n) 條邊）求解最小生成樹。
跑 kruskal 即可。所以總的復雜度是優秀的 O(n^2log n)。

@accepted code@

#include<cmath> #include<vector> #include<cstdio> #include<iostream> #include<algorithm> using namespace std; typedef long long ll; const int MAXN = 2500 + 10; const ll INF = (1LL<<60); struct edge{int u, v; ll d;edge(int _u=0, int _v=0, ll _d=0):u(_u), v(_v), d(_d){}friend bool operator < (edge a, edge b) {return a.d < b.d;} }edges[2*MAXN]; int fa[MAXN]; int find(int x) {return fa[x] = (fa[x] == x) ? x : find(fa[x]); } ll m, x[MAXN], y[MAXN]; int n; ll dist(int i, int j) {return ll(sqrt((x[i]-x[j])*(x[i]-x[j]) + (y[i]-y[j])*(y[i]-y[j]))); } vector<pair<int, ll> >G[MAXN]; void addedge(int u, int v, ll d) {G[u].push_back(make_pair(v, d));G[v].push_back(make_pair(u, d)); } void dfs(int x, int f, ll d) {if( x == n + 2 ) {printf("%lld\n", d - 1);return ;}for(int i=0;i<G[x].size();i++)if( G[x][i].first != f )dfs(G[x][i].first, x, max(d, G[x][i].second)); } int main() {scanf("%d%lld", &n, &m);edges[1] = edge(n + 1, n + 2, m/2 + 1);for(int i=1;i<=n;i++) {scanf("%lld%lld", &x[i], &y[i]);for(int j=1;j<i;j++)edges[i+j] = edge(i, j, dist(i, j)/2 + 1);edges[2*i] = edge(i, n + 1, y[i]/2 + 1);edges[2*i+1] = edge(i, n + 2, (m - y[i])/2 + 1);sort(edges + 1, edges + 2*i + 2);for(int j=1;j<=n+2;j++)fa[j] = j, G[j].clear();int cnt = 0;for(int j=1;j<=2*i+1;j++) {if( find(edges[j].u) != find(edges[j].v) ) {fa[find(edges[j].u)] = find(edges[j].v);edges[++cnt] = edges[j];}}for(int j=1;j<i+2;j++)addedge(edges[j].u, edges[j].v, edges[j].d);dfs(n + 1, -1, -INF);} }

@details@

康復計劃 - 1。

還好。沒有什么大的問題。我能記得最小生成樹有這個經典應用感覺已經很奇跡了。

只是看題解之前差點就要寫 lct 了。

轉載于:https://www.cnblogs.com/Tiw-Air-OAO/p/11072195.html

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的@noi.ac - 488@ cleaner的全部內容，希望文章能夠幫你解決所遇到的問題。

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