YACS20227月-观光电梯

课外活动时间，班级同学排队乘坐观光电梯欣赏美景。每次乘坐电梯的人数不得超过4人。班级学生自由组队，共分成了若干个组，第i个组的人数为ai，且每个组的人数均不超4个人。

由于每个学生都希望和自己的组员搭乘同一班电梯，因此同一小组的成员不能被安排在两班电梯上。请你帮助小爱老师计算一下，如何安排乘坐观光电梯的顺序，学生们能在最少次数内都乘坐到观光电梯？

输入： 3，2，4，1，3

输出： 4

这道题一开始我的想法 是计算a[i] 和 a[i+1] 的和，大于4就不能一部电梯。不过，这个思路做的话，只有20分；后来我意识到，这个安排是可以打乱顺序的。所以我们要自己想好分配的方法。

因此，这道题本质上是用贪心问题来思考。

首先，计算4人小队的个数，这些肯定是要占用一部电梯的；

其次，计算1，3小队的个数，让它们拼搭；至于为什么不是1，1，2这样的组合，可以用举列子的方式来表达，不过我纯粹是想不明白怎么做。。。min(cnt[3],cnt[1])，

接着计算2人小队的个数，个数整除2，也是占用的电梯数；

3人队有剩下的（就是说1人的已经全部分配完了）就是单独一个电梯，剩下的2人小队也是单独一个电梯；

3人队没有剩下的，就是1人剩下的，可以和2人队剩下的合并看看；ans=(cnt[1]+cnt[2]*2+3)/4

(这里是除以4上取整,多用一部电梯)

#include<bits/stdc++.h>

using namespace std;

int cnt[5],ans,x;

int main(){



  while (cin>>x){

    cnt[x]++;

  }



  ans=ans+cnt[4];

  int mat=min(cnt[3],cnt[1]);

  ans=ans+mat;

  cnt[1]=cnt[1]-mat;

  cnt[3]-=mat;

  ans+=cnt[2]/2;cnt[2]%=2;

  if (cnt[3]==0){

  ans+=(cnt[1]+cnt[2]*2+3)/4;

  }

  else ans+=cnt[3]+cnt[2];

  cout<<ans;

return 0;

}