二分/模拟-51Nod 1279-扔盘子

快来打我* 2022-04-18 05:22 185阅读 0赞

## 题目链接：[1279扔盘子][1279] ##

## 题目大意： ##

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

## 思路： ##

如果简单的暴力会超时，对井的每一层可做优化。

如果上一层比下一层窄，那么盘子肯定在上一层被卡，所以不妨把下一层的宽度也设为上一层的宽度，以此，井由上至下会变成一个非递增序列，便于查找。

## 二分解法： ##

将井“倒过来”，变成一个非递减序列，设置一个下界，查找盘子所能落到的最底位置，更新下界，直到盘子不能入井。

#include<iostream>
    #include<algorithm>
    using namespace std;
    
    #define min(a,b) (a<b?a:b)
    #define INF 1<<30
    #define MAX_SIZE 50005
    
    int Depth[MAX_SIZE];
    int N,M;
    int Up_Bound;
    
    int Binary_Search(int Width)
    {
        int l=Up_Bound,r=N;
    
        while(l<=r)
        {
            int mid=(l+r)/2;
            if(Width<=Depth[mid])
                r=mid-1;
            else
                l=mid+1;
        }
    
        return l<=N? Up_Bound=l+1 : 0;    //l>N放不下，返回0，否则返回新的下界
    }
    
    int main()
    {
        while(cin>>N>>M)
        {
            Up_Bound=0;
            int Res=0;
            int StopFlag=0;
            int Width;
            Depth[0]=INF;
            for(int i=1;i<=N;i++)
            {
                cin>>Depth[i];
                Depth[i]=min(Depth[i],Depth[i-1]);    //预处理，取上下层窄
            }
            sort(Depth+1,Depth+N+1);//倒序
    
            for(int i=1;i<=M;i++)
            {
                cin>>Width;
                if(!Binary_Search(Width))//查找盘子能到最底的位置
                    StopFlag=1;
    
                if(StopFlag)    //井放不下，只输入不做处理
                    continue;
                Res++;
            }
            cout<<Res<<endl;
        }
        return 0;
    }

## 纯暴力： ##

#include<stdio.h>
    #define MAX_SIZE 50005
    
    int Depth[MAX_SIZE];
    int NowMaxDepth;
    int N,M,Plate;
    int cnt=0;
    
    
    int main()
    {
        scanf("%d%d",&N,&M);
        NowMaxDepth=N;
        for(int i=1;i<=N;i++)
            scanf("%d",&Depth[i]);
    
        for(int i=1;i<=M;i++)
        {
            scanf("%d",&Plate);
            if(NowMaxDepth<=0)
                continue;
            int j;
            for(j=1;j<=NowMaxDepth;j++)
                if(Plate>Depth[j])
                    break;
            if(j>NowMaxDepth)    //每一层宽度都大于盘，落到当前的底，-1
                NowMaxDepth-=1;
            else                //盘子被卡住，-2
                NowMaxDepth=j-2;
            if(NowMaxDepth!=-1)
                cnt++;
            //cout<<"Now: "<<NowMaxDepth<<endl;
        }
        printf("%d\n",cnt);
    }

[1279]: https://www.51nod.com/Challenge/Problem.html#!%23problemId=1279