acwing周赛 排队问题--二分+单调栈的思想

项目场景：

二分+单调栈

---

问题描述

n 个小朋友排成一排，从左到右依次编号为1∼n。

第 i个小朋友的身高为 hi。

虽然队伍已经排好，但是小朋友们对此并不完全满意。

对于一个小朋友来说，如果存在其他小朋友身高比他更矮，却站在他右侧的情况，该小朋友就会感到不满。

每个小朋友的不满程度都可以量化计算，具体来说，对于第 i 个小朋友：

• 如果存在比他更矮且在他右侧的小朋友，那么他的不满值等于其中最靠右的那个小朋友与他之间的小朋友数量。
• 如果不存在比他更矮且在他右侧的小朋友，那么他的不满值为 −1。

请你计算并输出每个小朋友的不满值。

注意，第 1个小朋友和第 2 个小朋友之间的小朋友数量为 0，第 1 个小朋友和第 4 个小朋友之间的小朋友数量为 2。

输入格式

第一行包含整数 n。

第二行包含 n 个整数 h1,h2,…,hn。

输出格式

共一行，输出 n 个整数，第 i个整数为第 i个小朋友的不满值。

数据范围

前 55 个测试点满足2≤n≤5。
所有测试点满足 2≤n≤105，1≤hi≤109。

输入样例1：

6
10 8 5 3 50 45

输出样例1：

2 1 0 -1 0 -1

输入样例2：

7
10 4 6 3 2 8 15

输出样例2：

4 2 1 0 -1 -1 -1 

输入样例3：

5
10 3 1 10 11

输出样例3：

1 0 -1 -1 -1 

---

算法分析：

从左到右扫描数组，生成一个单调递增栈（栈中保存下标），任何一数 x 的答案，一定在栈中。

单调栈中保存的是数组下标，且下标对应的数组中的数字递增。所以，对于数组中的数字 x ,可以用二分法找到答案。

答案就是：在递增数组中，二分找出比 x 小的最大数。

---

实现代码：

 #include
 using namespace std;
 const int N = 100010;
 int w[N];
 int n;
 int st[N];
 int ans[N];
 int top = 0;
 int main(){
     int n;
     cin>>n;
     //从左到右构造一个单调递增的栈
     for(int i=0;i
         cin>>w[i];
         while(top>0 && w[i]
             top--;
         }
         st[++top] = i;//元素入栈
     }
     
     
     //在构造的单调栈中通过二分找出答案
     for(int i=0;i
         int l =0,r = top;
         while(l
             int mid = l+r+1>>1;
             //因为要找的答案是小于x的数 所以这里的判断语句只能是大于等于 取不到mid这个点 
             //所以要找的答案一定在mid左边 取不到mid这个点 r = mid-1
             if(w[st[mid]]>=w[i]) r = mid-1;
             else l = mid;
         }
         //要找到特定答案必须有两个条件 1.这个点在指定元素的右边 2.这个点的值小于指定元素
         if(st[r]>i && w[st[r]]-1<<" ";
         else cout<<"-1"<<" ";
     }
     return 0;
 }