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;
}