4.12 每日一题题解

车辆安排

• 题目链接：https://ac.nowcoder.com/acm/contest/112/B

涉及知识点：

• 贪心

solution：

• (祝大家周末愉快)
• (因为每队人数小于等于5，所以根据不同的人数，可以划分为五种不同的队伍)
• (考虑贪心，尽可能的让每个车上都塞满5个人)
• (5人，一队一辆车)
• (4人，应该和1人凑)
• (3人，应该和2人凑，如果还有剩余3人，就要和两个1人凑)
• (2人，先两个2人和1人凑，如果2人的个数还有1个，那就要和三个1人凑)
• (1人，五个1人凑一车)
• (至于代码实现，可以根据情况讨论)
• (不过n不是很大，我们可以扔到while循环里)

std:

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int b[10];
int main()
{
    int n,x,y,ans = 0;
    cin>>n;
    for(int i=1;i<=n;i++)cin>>x,b[x]++;
    while(n){
        ans++;
        int k = 5;
        for(int i=5;i>=1;i--){
            while(k >= i && b[i])
                k -= i,b[i]--,n--;
        }
    }
    cout<<ans<<endl;
    return 0;
}