【Codeforces】158B - Taxi

版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。

本文链接：https://blog.csdn.net/weixin_42449444/article/details/100524263

Problem Description：

After the lessons n groups of schoolchildren went outside and decided to visit Polycarpus to celebrate his birthday. We know that the i-th group consists of

s_{i}

friends (1 ≤ 

s_{i}

 ≤ 4), and they want to go to Polycarpus together. They decided to get there by taxi. Each car can carry at most four passengers. What minimum number of cars will the children need if all members of each group should ride in the same taxi (but one taxi can take more than one group)?

Input Specification:

The first line contains integer n (1 ≤ n ≤ 105) — the number of groups of schoolchildren. The second line contains a sequence of integers

s_{1}

, 

s_{2}

, ..., 

s_{n}

(1 ≤ 

s_{i}

 ≤ 4). The integers are separated by a space,

s_{i}

is the number of children in the i-th group.

Output Specification:

Print the single number — the minimum number of taxis necessary to drive all children to Polycarpus.

Sample Input1:

5
1 2 4 3 3

Sample Output1:

4

Sample Input2:

8
2 3 4 4 2 1 3 1

Sample Output2:

5

解题思路：

我一开始就是直男思维，这不就是贪心算法吗？然后我直接在输入的时候安排座位 尽可能地把车坐满4个人，最后输出有几辆车坐了人即可。

正在播放五五开名场面.mp4：“单测一波样例，傻逼，直接把样例过了，点击submit。 评测姬你快点，评测姬你这都还没开测的嘛，评测姬你快点啊！别磨磨蹭蹭的。 Running on test 1,2,3,4,5,6,7,8,9,10......nice 给评测姬倒一杯茶好吧，给评测姬，倒一杯卡布奇诺。大组数据pass，pass，漂亮！ 最后一组数据你能卡我？你能卡掉我？你这道题能出一组测试用例把我的代码卡了，我当场，就把这个电脑屏幕，吃掉！” Wrong answer on test 52！ 开始战术咳嗽......咳呵咳

太真实了.jpg 我碰到了这组测试用例，预期输出应该是3而实际输出的是4。

8
1 1 2 1 1 1 3 2

步入正题 下面是正确的思路：贪心算法，尽可能地坐满4个人，4人可以直接开走，3人只能和1搭配，2人尽量和2人搭配，剩下的1人尽可能坐满4人。昂~我注释写得应该很容易理解啦。

AC代码：WA代码：

#include <bits/stdc++.h>
using namespace std;
#define Up(i,a,b) for(int i = a; i <= b; i++)
#define ms(a,x) memset(a,x,sizeof(a))

int main()
{
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    int s[n+1], car[n+1];
    ms(car,0);
    Up(i,1,n)
    {
        cin >> s[i];
        Up(j,1,n)
        {
            if(car[j]+s[i] <= 4)
            {
                car[j] += s[i];
                break;
            }
        }
    }
    int cnt = 0;
    for(auto it : car)
    {
        if(it)
        {
            cnt++;
        }
    }
    cout << cnt << endl;
    return 0;
}

AC代码：

#include <bits/stdc++.h>
using namespace std;
#define Up(i,a,b) for(int i = a; i <= b; i++)

int main()
{
    ios::sync_with_stdio(false);
    int n,cnt = 0;
    cin >> n;
    int a[5]={0};    //a[i]表示有a[i]组是i个人一起搭车的
    Up(i,1,n)
    {
        int _;
        cin >> _;
        a[_]++;
    }
    int _ = min(a[1],a[3]);   //3只能和1搭配,所以优先考虑3
    a[1] -= _;
    a[3] -= _;
    cnt += _ + a[3] + a[4] + a[2]/2;    //4直接加,2要和2搭配
    if(a[2]&1)   //若2人一组的是奇数
    {
        cnt++;
        if(a[1]>=2)
        {
            a[1] -= 2;
        }
        else if(a[1]==1)   //不足2人
        {
            a[1]--;
        } 
    }
    cnt += a[1]/4 + (a[1]%4 ? 1 : 0);   //剩下的1尽可能地坐满
    cout << cnt << endl;
    return 0;
}