首页 > 代码库 > Code Forces Gym 100971D Laying Cables（单调栈）
Code Forces Gym 100971D Laying Cables（单调栈）
D - Laying Cables
Time Limit:2000MS Memory Limit:262144KB 64bit IO Format:%I64d & %I64u
One-dimensional country has n cities, the i-th of which is located at the point xi and has population pi, and all xi, as well as all pi, are distinct. When one-dimensional country got the Internet, it was decided to place the main server in the largest city, and to connect any other city j to the city k that has bigger population than j and is the closest to it (if there are many such cities, the largest one should be chosen). City k is called a parent of city j in this case.
Unfortunately, the Ministry of Communications got stuck in determining from where and to where the Internet cables should be laid, and the population of the country is suffering. So you should solve the problem. For every city, find its parent city.
Input
The first line contains a single integer n (1 ≤ n ≤ 200000) — the number of cities.
Each of the next n lines contains two space-separated integers xi and pi (1 ≤ xi, pi ≤ 109) — the coordinate and the population of thei-th city.
Output
Output n space-separated integers. The i-th number should be the parent of the i-th city, or - 1, if the i-th city doesn‘t have a parent. The cities are numbered from 1 by their order in the input.
Sample Input
4
1 1000
7 10
9 1
12 100
-1 4 2 13
1 100
2 1
3 10
-1 1 13
1 10
3 100
2 1
2 -1 2
题意：给定一维数轴上的N个点和对应的权值，同时定义一个点的父亲为：离它最近且权值比它大的点下标，如果距离相同则选择权值较大的，如果没有则为-1，求出所有点的父亲？
思路1：单调栈预处理出左边和右边第一个比它大的元素的下标即可。
单调栈的作用：求出某个数的左边或右边第一个比它大或比它小的元素，复杂度O(n)。
单调递增栈：元素从栈底到栈顶严格单调递增。
单调递减栈：元素从栈底到栈顶严格单调递减。
代码1：
1 #include <iostream> 2 #include <queue> 3 #include <stack> 4 #include <cstdio> 5 #include <vector> 6 #include <map> 7 #include <set> 8 #include <bitset> 9 #include <algorithm>10 #include <cmath>11 #include <cstring>12 #include <cstdlib>13 #include <string>14 #include <sstream>15 #define x first16 #define y second17 #define pb push_back18 #define mp make_pair19 #define lson l,m,rt*220 #define rson m+1,r,rt*2+121 #define mt(A,B) memset(A,B,sizeof(A))22 #define mod 100000000723 using namespace std;24 typedef long long LL;25 const int N=200000+10;26 const LL INF=0x3f3f3f3f3f3f3f3fLL;27 LL val[N],id[N],x[N],ans[N],S[N],L[N],R[N];//S[N]表示单调栈28 bool cmp(LL a,LL b)29 {30 return x[a]<x[b];31 }32 int main()33 {34 #ifdef Local35 freopen("data.txt","r",stdin);36 #endif37 ios::sync_with_stdio(0);38 LL i,j,k,n;39 cin>>n;40 for(i=1;i<=n;i++)41 {42 cin>>x[i]>>val[i];//x[i]表示在数轴上的位置，val[i]表示该点的价值43 id[i]=i;44 }45 sort(id+1,id+1+n,cmp);//按在数轴上的位置从小到大排序46 k=0;S[k++]=0;val[0]=2e9;//先把INF压入栈底47 for(i=1;i<=n;i++)48 {49 while(val[S[k-1]]<=val[id[i]])k--;//如果当前的val比栈顶的大，就把栈顶的元素弹出来50 L[id[i]]=S[k-1];//找到了左边第一个比他大的数的下标51 S[k++]=id[i];//把当前的下标压入栈52 }53 k=n+1;S[k--]=n+1;val[n+1]=2e9;54 for(i=n;i>=1;i--)//同理55 {56 while(val[S[k+1]]<=val[id[i]])k++;57 R[id[i]]=S[k+1];58 S[k--]=id[i];59 }60 for(i=1;i<=n;i++)61 {62 if(L[i]==0&&R[i]==n+1)ans[i]=-1;63 else if(L[i]==0)ans[i]=R[i];64 else if(R[i]==n+1)ans[i]=L[i];65 else66 {67 if(abs(x[L[i]]-x[i])<abs(x[R[i]]-x[i]))ans[i]=L[i];68 else if(abs(x[L[i]]-x[i])>abs(x[R[i]]-x[i]))ans[i]=R[i];69 else70 {71 if(val[L[i]]<val[R[i]])ans[i]=R[i];72 else if(val[L[i]]>val[R[i]])ans[i]=L[i];73 }74 }75 }76 for(i=1;i<=n;i++)77 {78 if(i==n)cout<<ans[i]<<endl;79 else cout<<ans[i]<<" ";80 }81 }
思路2：先按数轴上的位置排序，RMQ预处理区间的最大值，再往左往右二分。训练的时候并不会单调栈，所以只能用RMQ二分瞎几把乱搞。
代码2：
1 #include <iostream> 2 #include <queue> 3 #include <stack> 4 #include <cstdio> 5 #include <vector> 6 #include <map> 7 #include <set> 8 #include <bitset> 9 #include <algorithm> 10 #include <cmath> 11 #include <cstring> 12 #include <cstdlib> 13 #include <string> 14 #include <sstream> 15 #define lson l,m,rt*2 16 #define rson m+1,r,rt*2+1 17 #define mod 1000000007 18 #define mt(A) memset(A,0,sizeof(A)) 19 using namespace std; 20 typedef long long LL; 21 const int N=200000+10; 22 const LL INF=0x3f3f3f3f3f3f3f3fLL; 23 LL dp[N][30]; 24 int ans[N]; 25 struct node 26 { 27 LL dis,val; 28 int id; 29 } a[N],b[N]; 30 bool cmp(struct node a,struct node b) 31 { 32 if(a.dis!=b.dis)return a.dis<b.dis; 33 else return a.val>b.val; 34 } 35 void RMQ(int n) 36 { 37 for(int i=1; i<=n; i++)dp[i][0]=a[i].val; 38 for(int j=1; (1<<j)<=n; j++) 39 { 40 for(int i=1; (i+(1<<j)-1)<=n; i++) 41 { 42 dp[i][j]=max(dp[i][j-1],dp[i+(1<<(j-1))][j-1]); 43 } 44 } 45 } 46 LL query(int l,int r) 47 { 48 int k=0; 49 while((1<<(k+1))<=(r-l+1))k++; 50 return max(dp[l][k],dp[r-(1<<k)+1][k]); 51 } 52 struct node found(int l,int r,LL Val)//you 53 { 54 int mid; 55 struct node p1; 56 LL V; 57 while(l<r) 58 { 59 mid=(l+r)/2; 60 V=query(l,mid); 61 if(V>Val) 62 { 63 r=mid; 64 } 65 else 66 { 67 l=mid+1; 68 } 69 } 70 //cout<<l<<" "<<r<<endl; 71 if(a[l].val>Val)p1=a[l]; 72 else p1.id=-1; 73 return p1; 74 } 75 struct node found1(int l,int r,LL Val)//you 76 { 77 int mid; 78 struct node p1; 79 LL V; 80 while(l<=r) 81 { 82 mid=(l+r)/2; 83 V=query(mid,r); 84 if(V>Val) 85 { 86 l=mid+1; 87 } 88 else 89 { 90 r=mid-1; 91 } 92 } 93 //cout<<l<<" "<<r<<endl; 94 if(a[r].val>Val)p1=a[r]; 95 else p1.id=-1; 96 return p1; 97 } 98 int main() 99 {100 #ifdef Local101 freopen("data","r",stdin);102 #endif103 int i,j,k,n;104 cin>>n;105 for(i=1; i<=n; i++)106 {107 scanf("%lld%lld",&a[i].dis,&a[i].val);108 a[i].id=i;109 b[i]=a[i];110 }111 sort(a+1,a+n+1,cmp);112 RMQ(n);113 for(i=1; i<=n; i++)114 {115 int l,r,mid;116 struct node p1,p2;117 p1.id=-1;p2.id=-1;118 LL V;119 l=1;120 r=i;121 p1=found1(l,r,a[i].val);122 l=i;r=n;123 p2=found(l,r,a[i].val);124 //cout<<i<<" "<<p1.id<<" "<<p2.id<<endl;125 if(p2.id==-1&&p1.id==-1)ans[a[i].id]=-1;126 else if(p1.id==-1&&p2.id!=-1)ans[a[i].id]=p2.id;127 else if(p1.id!=-1&&p2.id==-1)ans[a[i].id]=p1.id;128 else129 {130 if(abs(a[i].dis-p1.dis)>abs(a[i].dis-p2.dis))131 {132 ans[a[i].id]=p2.id;133 }134 else if(abs(a[i].dis-p1.dis)<abs(a[i].dis-p2.dis))135 {136 ans[a[i].id]=p1.id;137 }138 else139 {140 if(p1.val>p2.val)ans[a[i].id]=p1.id;141 else ans[a[i].id]=p2.id;142 }143 }144 }145 for(i=1;i<=n;i++)146 {147 if(i==n)printf("%d\n",ans[i]);148 else printf("%d ",ans[i]);149 }150 }
Code Forces Gym 100971D Laying Cables（单调栈）