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

· · 题解

无论一个管子的半径多长，只要它上面有比它半径小的管子，它的长就毫无意义。 即一个管子真正有效的半径长度是它之上所有半径长中的最小值

然后按管子从下到上，盘子从前到后的顺序，类似乎归并排序的实现

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int S=300030;
ll r[S]; ll k[S]; 
int n,m;
int main()
{
    scanf("%d %d",&n,&m);
    for(int i=n;i>=1;i--) scanf("%lld",&r[i]);//倒着输入，方便处理
        //r数组中从下到上储存“有效”的半径长度，就是毫无阻碍时能够掉下来
            //的最大值
    for(int i=1;i<=m;i++) scanf("%lld",&k[i]);//盘子顺序
    for(int i=n-1;i>=1;i--)
        r[i]=min(r[i],r[i+1]);

    int head_1=1; //第head_1个管子
    int head_2=1;//第head_2个盘子
    while(head_1<=n && head_2<=m)
    {
        if(r[head_1]>=k[head_2])
        {
            head_1++; head_2++;
        }
        else
            head_1++;
    }
    if(head_2<=m)//若盘子未全部放进，则输出0
        printf("0\n");
    else//可以全部放入，换算出结果
        printf("%d\n",n-(head_1-1)+1);
    return 0;
}