题解 P3434 【[POI2006]KRA-The Disks】

_Lemon_ · 2017-07-21 16:11:10 · 题解

本题其实并不难

首先我们可以建一个数组cl，保存此位置之前最窄的管子大小。

再从最底下扫一遍，依次看看盘子会卡在哪里；

最后如果最后一个没进去就到顶部，则输出0；

否则输出最后一个卡在哪里。

请注意这里管子的宽度是从上到下输入的，所以上方的先输入。

#include<bits/stdc++.h>
using namespace std;
int cl[300001],now,n,m,pan[300001],guan[300001];
int main()
{
    int i,step;
    cin>>n>>m;
    step=n;
    for(i=1;i<=n;i++)
      scanf("%d",&guan[i]);
    for(i=1;i<=m;i++)
      scanf("%d",&pan[i]);
    cl[1]=guan[1];
    for(i=2;i<=n;i++)
      if(cl[i-1]<guan[i]) cl[i]=cl[i-1];
         else cl[i]=guan[i];//记录i之前最窄的位置的宽度。
    for(i=1;i<=m;i++)
     { 
      while(cl[step]<pan[i]) step--; //如果放不下，则向上走。
      step--;
      if(step==0) {
                        cout<<'0';
                        return 0;//如果step超出了最高的管子，直接输出0，结束程序。
                  }
     }
     cout<<step+1;//否则输出最后的位置。
     return 0; 
}