[洛谷 3434][POI2006]KRA-The Disks

题目链接

https://www.luogu.com.cn/problem/P3434

题解

只需扫描两次即可解决问题。

第一次维护前缀最小值，第二次用一个指针维护当前所在位置，每个圆盘下落时，将指针向前移动，直到前缀最小值不小于当前盘直径即可。

#include <iostream>
#include <algorithm>
using namespace std;
int r[300005],a[300005];
int main()
{
 int n,m;
 cin>>n>>m;
 a[0]=2e9;
 for(int i=1;i<=n;i++)
 {
  cin>>r[i];
  a[i]=min(a[i-1],r[i]);
 }
 int cur=n;
 for(int i=1;i<=m;i++)
 {
  int k;
  cin>>k;
  while(a[cur]<k)
   cur--;
  if(cur&&i!=m)cur--;
 }
 cout<<cur<<endl;
 return 0;
}