题解 P2816 【宋荣子搭积木】

gyfer · 2017-10-06 14:14:37 · 题解

这题竟然是普及＋

先考虑这样一个问题，你现在有若干列盒子。现在有一个新的盒子，你只能挑一列，把新盒子放到最底下。为了后续策略最优，你应该怎么放？

显然是应该找（能放的）个数最多的那个放

因为这样放，对于后续的操作来说才是最优的。

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

所以我们就有了一种贪心的方法。先将所有的盒子按照承载量从小到大排序。

然后我们开一个数组，记录一下当前一共有多少列，每一列一共有多少个盒子。从小到大扫描所有的盒子，找到能放下的数量最多的列，放进去。如果没有任何一列能放下，则建一个新列。

如目前：2，4，6。新来了一个承载量5的盒子，就应该放在『4』那一列。

举例：0，1，1，2，2，3

这是纯模拟题啊，代码如下：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<fstream>
#include<cstring>
using namespace std;
int n,m,a[5001],i,j,lie[5001];//a存状态，lie模拟摆放
int main(){
  cin>>n;
  for(int i=1;i<=n;i++) cin>>a[i];
  sort(a+1,a+n+1);
  m=1;
  lie[m]=1;
  for(int i=2;i<=n;i++){
        bool fool=true;
    for(int j=1;j<=m;j++) if(lie[j]<=a[i]){
        lie[j]++;
        fool=false;
        break;
    }
    if(fool) m++,lie[m]=1;
  }
  cout<<m<<endl;
}