1279 扔盘子

1.0 秒 131,072.0 KB 5 分 1级题

有一口井，井的高度为N，每隔1个单位它的宽度有变化。现在从井口往下面扔圆盘，如果圆盘的宽度大于井在某个高度的宽度，则圆盘被卡住（恰好等于的话会下去）。

盘子有几种命运：1、掉到井底。2、被卡住。3、落到别的盘子上方。

盘子的高度也是单位高度。给定井的宽度和每个盘子的宽度，求最终落到井内的盘子数量。

如图井和盘子信息如下：

井：5 6 4 3 6 2 3

盘子：2 3 5 2 4

最终有4个盘子落在井内。

本题由 @javaman 翻译。

输入

第1行：2个数\(N, M\)中间用空格分隔，\(N\)为井的深度，\(M\)为盘子的数量\((1 \leq N, M \leq 50000)\)。

第\(2\) ~ \(N + 1\)行，每行\(1\)个数，对应井的宽度\(W_i(1 \leq W_i \leq 10^9)\)。

第\(N + 2\) ~ \(N + M + 1\)行，每行\(1\)个数，对应盘子的宽度\(D_i(1 \leq D_i \leq 10^9)\)

输出

输出最终落到井内的盘子数量。

输入样例

7 5

5

6

4

3

6

2

3

2

3

5

2

4

输出样例

4

思路

第\(i\)层能够通过的盘子宽度为第\(i\)层上面的所有层数的最小宽度。这样处理以后，就井的每层宽度就变成了一个非递增序列，我们可以用二分或单调栈来查找

二分

以最上面那个盘子所在的位置为起始位置，进行二分，查找下一个盘子可以落到的位置，判断该位置是否可行，如果可行，盘子数量加一，更新最上面盘子的位置为当前查找到的位置\(+1\)，否则，停止

单调栈

用单调栈来维护序列的非递增性。能够加入单调栈的盘子数量即为能落入井内的盘子数量

代码

二分

#include <bits/stdc++.h>

#define ll long long

#define ull unsigned long long

#define ms(a,b) memset(a,b,sizeof(a))

const int inf=0x3f3f3f3f;

const ll INF=0x3f3f3f3f3f3f3f3f;

const int maxn=1e6+10;

const int mod=1e9+7;

const int maxm=1e3+10;

using namespace std;

int jing[maxn];

int pan[maxn];

int main(int argc, char const *argv[])

{

    #ifndef ONLINE_JUDGE

        freopen("/home/wzy/in.txt", "r", stdin);

        freopen("/home/wzy/out.txt", "w", stdout);

        srand((unsigned int)time(NULL));

    #endif

    ios::sync_with_stdio(false);

    cin.tie(0);

    int n,m;

    cin>>n>>m;

    jing[0]=inf;

    for(int i=1;i<n+1;i++)

    {

        cin>>jing[i];

        if(jing[i]>jing[i-1])

            jing[i]=jing[i-1];

    }

    sort(jing+1,jing+1+n);

    int pos=1;

    int ans=0;

    for(int i=1;i<m+1;i++)

        cin>>pan[i];

    for(int i=1;i<m+1;i++)

    {

        pos=lower_bound(jing+pos,jing+n+1,pan[i])-jing;

        if(pos==n+1)

            break;

        ans++;

        pos++;

    }

    cout<<ans<<endl;

    #ifndef ONLINE_JUDGE

        cerr<<"Time elapsed: "<<1.0*clock()/CLOCKS_PER_SEC<<" s."<<endl;

    #endif

    return 0;

}

单调栈

#include <bits/stdc++.h>

#define ll long long

#define ull unsigned long long

#define ms(a,b) memset(a,b,sizeof(a))

const int inf=0x3f3f3f3f;

const ll INF=0x3f3f3f3f3f3f3f3f;

const int maxn=1e6+10;

const int mod=1e9+7;

const int maxm=1e3+10;

using namespace std;

int jing[maxn];

int pan[maxn];

int main(int argc, char const *argv[])

{

    #ifndef ONLINE_JUDGE

        freopen("/home/wzy/in.txt", "r", stdin);

        freopen("/home/wzy/out.txt", "w", stdout);

        srand((unsigned int)time(NULL));

    #endif

    ios::sync_with_stdio(false);

    cin.tie(0);

    int n,m;

    cin>>n>>m;

    jing[0]=inf;

    stack<int>st;

    for(int i=1;i<n+1;i++)

    {

        cin>>jing[i];

        jing[i]=min(jing[i],jing[i-1]);

        st.push(jing[i]);

    }

    int ans=0;

    for(int i=1;i<m+1;i++)

    {

        cin>>pan[i];

        while(st.size())

        {

            if(pan[i]<=st.top())

            {

                st.pop();

                ans++;

                break;

            }

            else

                st.pop();

        }

    }

    cout<<ans<<endl;

    #ifndef ONLINE_JUDGE

        cerr<<"Time elapsed: "<<1.0*clock()/CLOCKS_PER_SEC<<" s."<<endl;

    #endif

    return 0;

}

巴特西

51Nod 1279：扔盘子（二分||单调栈）

1279 扔盘子

输入

输出

输入样例

输出样例

思路

二分

单调栈

代码

二分

单调栈

最新文章

热门文章