51Nod－1279－扔盤子

ACM模版

描述

題解

這道題最直覺的思路是從第一個圓蓋開始往裡邊填，一直填到不能填，這個思路是順向思維，複雜度為O(N^2)，事實證明，這樣子會逾時，是以，我們需要想一個複雜度更低的思路，這時，我們可以逆向思維來考慮。首先分析可知，如果盤子可以落到n，那麼比n淺的深度的寬度必須都大于等于n位置的寬度，那麼我們可以預處理一下井，使得井從深往淺，寬度遞增。這樣，我們填圓蓋時可以直接從最底層開始填充，一直填到結束出結果，這樣的複雜度為O(n)，可以完美AC……

代碼

#include <iostream>
#include <cstdio>

using namespace std;

const int MAXN =  + ;
const int INF =  + ;

int width[MAXN] = {INF};

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

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

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

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