有一口井,井的高度为N,每隔1个单位它的宽度有变化。现在从井口往下面扔圆盘,如果圆盘的宽度大于井在某个高度的宽度,则圆盘被卡住(恰好等于的话会下去)。
盘子有几种命运:1、掉到井底。2、被卡住。3、落到别的盘子上方。
盘子的高度也是单位高度。给定井的宽度和每个盘子的宽度,求最终落到井内的盘子数量。
如图井和盘子信息如下:
井:5 6 4 3 6 2 3
盘子:2 3 5 2 4
最终有4个盘子落在井内。



题解:一开始想模拟盘子进井,然后更新井底,果断TLE,因为数据比较大,O(n^2)了。然后根据题目标签“单调栈”,于是我们可以先遍历一遍求出从井口到第n层中每层能通过的最大值(也就是求前面的最小值)。从井口到井底全部入栈,然后第一个盘子开始从井底进入,并且检查最大值能否使得盘子通过,如果不通过则一直出栈,依次类推。


代码:

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <stack>
using namespace std;
const int inf=0x3f3f3f3f;
const int maxn= 50005;
int n, m, x, mi[maxn], disk[maxn], ans;
int main()
{
    while(~scanf("%d%d", &n, &m)){
        stack<int> jin;
        mi[0]=inf;
        for(int i=1;i<=n;i++){
            scanf("%d", &x);
            jin.push(x);
            mi[i]=min(mi[i-1], x);
        }
        for(int i=1;i<=m;i++){
            scanf("%d", &disk[i]);
        }
        ans=0;
        for(int i=1;i<=m;i++){
            while(jin.size()&&mi[jin.size()]<disk[i]){
                jin.pop();
            }
            if(jin.size()){
                ans++;
                jin.pop();
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}