20.2.4_T1: 小Z搭积木
题目描述:
小 Z 喜欢搭积木。小 Z 一共有 n 块积木，并且积木只能竖着一块一块的摞，可以摞多列。小 Z 的积木都是智能积木，第 i 块积木有一个情绪值 Xi。当摞在该积木上面积木总数超过 Xi 时，i 号积木就会不高兴。小 Z 情商这么高，肯定不希望有积木不高兴。但是他又希望每块积木都被用上，并且摞的积木列的总数最少。
思路:
非常明显的贪心：对于一块积木而言，它所在的位置越低，它上面的积木就越多，所以自然是要让情绪值大的积木在下面。将所有的积木从小到大排序，从上往下加积木，如果有一块积木不开心了就再开一列。
代码：
#include<cstdio>
#include<algorithm>
using namespace std;
int n,x[5005],v[5005],ans,m;
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&x[i]);
sort(x+1,x+n+1);
for(int i=1;i<=n;i++)
if(!v[i]){
ans++;
m=1;
for(int j=i+1;j<=n;j++)
if(!v[j]&&x[j]>=m){
v[j]=1;
m++;
}
}
printf("%d",ans);
return 0;
}