本文主要是介绍二分/模拟-51Nod 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 50005int 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;elsel=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 50005int 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) //每一层宽度都大于盘，落到当前的底，-1NowMaxDepth-=1;else //盘子被卡住，-2NowMaxDepth=j-2;if(NowMaxDepth!=-1)cnt++;//cout<<"Now: "<<NowMaxDepth<<endl;}printf("%d\n",cnt);
}
这篇关于二分/模拟-51Nod 1279-扔盘子的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
