[洛谷 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;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据