P2816 宋荣子搭积木

描述:https://www.luogu.com.cn/problem/P2816

saruka非常喜欢搭积木，他一共有n块积木。而且saruka的积木很特殊，只能一块块的竖着摞，可以摞很多列。说过saruka的是特殊的积木了，这些积木都非常智能，第i块积木有一个情绪值xi，当摞在这块积木上的积木总数超过xi时，这块积木就会很不高兴，发誓以后不会再和saruka一起玩耍了。saruka这么爱玩积木，肯定不会让积木不高兴的，但是saruka又希望每块积木都被用上，并且摞的积木列数最少。你能来帮帮saruka嘛？

考虑我们已经堆好了3列积木，现在来了一个新积木

我们该把它放在哪一列呢?

堆在上面是不好考虑的，因为我们不知道下面的积木是不是承受的了重量

所以我们考虑每次把新来的积木放在每一列的最下面

在放的下的前提下，我们尽量放在积木数最多的那一列下

因为后续的积木可能不能放在这一列(承受重量属性比较低)

比如原来是2，3，5，再放肯定要放在5的底下，变成2，3，6。对于后续的决策来说，2，3，6肯定比3，3，5或者2，4，5优。

那么我们先把积木从小到大排序

Ⅰ能放下的话，挑最高的积木那一列放

Ⅱ放不下的话，新开一列

#include <bits/stdc++.h>

using namespace std;

int n;

int a[],f=,w[];

int main()

{

    cin>>n;

    for(int i=;i<=n;i++)    cin>>a[i];

    sort(a+,a++n);

    w[]=;

    for(int i=;i<=n;i++)

    {

        int flag=;

        for(int j=;j<=f;j++)

        {

            if(a[i]>=w[j])

            {

                flag=;

                w[j]++;

                break;

            }

        }

        if(!flag){

            f++;

            w[f]++;

        }

    }

    cout<<f;

}

巴特西

P2816 宋荣子搭积木

最新文章

热门文章