Description

Input

輸入文件的第一行含有一個正整數 n，代表山的頂點數。
接下來 n 行，每行包含兩個整數 x i 和 y i ，代表一個頂點的坐標。輸入保證 x i單調遞增。

Output

輸出 n 行，第 i 行包含一個整數，代表從第 i 個頂點出發走到最高點需要經過多少段。

Sample Input

5
1 5
2 4
3 9
4 0
5 2

Sample Output

2
1
0
1
2

Data Constraint

Hint

Solution

• 我們設 l[i]?(r[i]) 表示點 i 向左（右）看能看到的點最高是哪一個。

• 這用單調棧可以 O(N) 求出來——左右掃一遍就可以了。

• 之后我們發現最難統計的就是一個點不斷發現新的高點，從而一直拐彎。

• 那么我們又設 fl[i]?(fr[i]) 表示點 i 向左（右）第一個能看到更高點的位置。

• 這我們也可以近乎 O(N) 求出來，一樣是掃一遍，用前面的 fl[] 更新當前的 fl[i] 。

• 那么點 i 能看到的最高高度就是 f[i]=max(fl[i],fr[i]) ，走的方向也就確定了。

• 之后我們以最高點為 root ，連邊 (fl[i],i) （或 fr[i] ，以走的方向而定）。

• 顯然這是一個樹結構，因為每個點始終會到最高點（一定連通），目標點又越來越高（沒環）。

• 于是跑一邊 dfs ，就能算出每個點走的段數了。

• 時間復雜度近乎 O(N) 。

Code

#include<cstdio> #include<cctype> using namespace std; const int N=2e5+5; struct data {int x;long long y; }a[N]; int top,tot,root; int first[N],nex[N],en[N]; int l[N],r[N],st[N],ans[N],fl[N],fr[N],fx[N]; long long f[N]; double d[N]; inline int read() {int X=0,w=0; char ch=0;while(!isdigit(ch)) w|=ch=='-',ch=getchar();while(isdigit(ch)) X=(X<<1)+(X<<3)+(ch^48),ch=getchar();return w?-X:X; } inline void write(int x) {if(x>9) write(x/10);putchar(x%10+'0'); } inline double get(int x,int y) {return (a[x].y-a[y].y)*1.0/(a[x].x-a[y].x); } inline int abs(int x) {return x<0?-x:x; } void dfs(int x) {for(int i=first[x];i;i=nex[i]){ans[en[i]]=ans[x]+abs(x-en[i]);dfs(en[i]);} } inline void insert(int x,int y) {nex[++tot]=first[x];first[x]=tot;en[tot]=y; } int main() {int n=read();for(int i=1;i<=n;i++) a[i].x=read(),a[i].y=read();for(int i=1;i<=n;i++){while(top>1 && d[top]<=get(i,st[top])) top--;if(a[st[top]].y>a[i].y) l[i]=st[top];st[++top]=i;if(top>1) d[top]=get(i,st[top-1]);}top=0;for(int i=n;i;i--){while(top>1 && d[top]>=get(i,st[top])) top--;if(a[st[top]].y>=a[i].y) r[i]=st[top]; else r[i]=n+1;st[++top]=i;if(top>1) d[top]=get(i,st[top-1]);}r[n]=n+1;for(int i=1;i<=n;i++) a[i].y=a[i].y*1000000+i;for(int i=1;i<=n;i++){long long h=a[i].y;if(a[r[i]].y>h) h=a[r[i]].y,fx[i]=2;if(a[l[i]].y>h) h=a[l[i]].y,fx[i]=1;f[i]=h;}for(int i=1;i<=n;i++){int j=i-1;while(j && f[i]>=f[j]) j=fl[j];fl[i]=j?j:l[i];}for(int i=n;i;i--){int j=i+1;while(j<=n && f[i]>=f[j]) j=fr[j];fr[i]=j<=n?j:r[i];}for(int i=1;i<=n;i++)if(!fx[i]) root=i; elseif(fx[i]==1) insert(fl[i],i); else insert(fr[i],i);dfs(root);for(int i=1;i<=n;i++) write(ans[i]),putchar('\n');return 0; }

總結

以上是生活随笔為你收集整理的JZOJ 3401 JZOJ 5673. 【GDOI2018Day1模拟4.20】爬山法的全部內容，希望文章能夠幫你解決所遇到的問題。

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