AcWing-第78场周赛

AcWing-第78场周赛

T3 AcWing 4721. 排队

算法(单调栈,二分)

对于$a_i$和$a_j$$(i>j)$，如果$a_i>=a_j$，那么$a_i$的存在就不必要了，因为我们需要找最右侧哪个小于当前数$a_k$的位置，即$a_k>a_i>=a_j$时，$a_j$是我们要找的最小的数，而不是$a_i$，因此满足以上条件的$(i,j)$对，我们都可以舍去$i$，具体的我们维护一个栈，栈顶是最小的元素，栈顶是最大的元素，栈顶到栈底是单调递增的，每当判断当前元素是否存在右侧最小的时候，我们需要判断当前栈中是否有元素，不存在则当前位置答案为1，否则判断当前数是否小于等于栈顶元素：

1. 小于等于：当前答案为-1
2. 大于：在栈中进行二分，找出小于当前元素最大的位置

最后插入当前位置时：只有栈中为空的时候或者栈顶的元素大于当前元素的时候才会进行插入操作。

C++代码

#include 
#include 
#include 

using namespace std;

const int N = 100010;

int n;
int h[N], stk[N];
int ans[N];

int main()
{
    scanf("%d", &n);
    for(int i = 0; i < n; i ++) scanf("%d", &h[i]);
    
    int top = 0;
    for(int i = n - 1; i >= 0; i --)
    {
        if(!top || h[i] <= h[stk[top]]) ans[i] = -1;
        else
        {
            int l = 1, r = top;
            while(l < r)
            {
                int mid = l + r >> 1;
                if(h[stk[mid]] < h[i]) r = mid;
                else l = mid + 1;
            }
            ans[i] = stk[r] - i - 1;
        }
        
        if(!top || h[i] < h[stk[top]]) stk[ ++ top] = i;
    }
    
    for(int i = 0; i < n; i ++)
        printf("%d ", ans[i]);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40