ACM模版

描述

题解

这道题最直观的思路是从第一个圆盖开始往里边填,一直填到不能填,这个思路是顺向思维,复杂度为O(N^2),事实证明,这样子会超时,所以,我们需要想一个复杂度更低的思路,这时,我们可以逆向思维来考虑。首先分析可知,如果盘子可以落到n,那么比n浅的深度的宽度必须都大于等于n位置的宽度,那么我们可以预处理一下井,使得井从深往浅,宽度递增。这样,我们填圆盖时可以直接从最底层开始填充,一直填到结束出结果,这样的复杂度为O(n),可以完美AC……

代码

#include <iostream>
#include <cstdio>

using namespace std;

const int MAXN = 5e4 + 10;
const int INF = 1e9 + 10;

int width[MAXN] = {INF};

int main(int argc, const char * argv[])
{
    int N, M;
    cin >> N >> M;

    for (int i = 1; i <= N; i++)
    {
        scanf("%d", width + i);
        if (width[i] > width[i - 1])
        {
            width[i] = width[i - 1];
        }
    }

    int res = 0;
    int flag = N;
    int plate;
    for (int i = 0; i < M; i++)
    {
        scanf("%d", &plate);
        for (; flag > 0; flag--)
        {
            if (width[flag] >= plate)
            {
                flag--;
                res++;
                break;
            }
        }
    }

    std::cout << res << '\n';
    return 0;
}