CodeForces – 158B.Taxi (贪心)

CodeForces – 158B.Taxi (贪心)

题意分析

首先对1234的个数分别统计，4人组的直接加上即可。然后让1和3成对处理，只有2种情况，第一种是1多，就让剩下的1和2组队处理，另外一种是3多，那么结果就加上3的个数，再单独处理2.

对于1和2组队处理的讨论：首先分配2，有2种情况，一种是2正好分配完了，另外一种就2还剩下2个人(正好剩下1组)。就一起处理这个2个人和1剩下的人。

把每次处理的结果都加起来即可。

代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <sstream>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#define INF 0x3f3f3f3f
#define nmax 5
#define MEM(x) memset(x,0,sizeof(x))
using namespace std;
int a[nmax];
int main()
{
    //freopen("in.txt","r",stdin);
    int n;
    while(scanf("%d",&n) != EOF){
        MEM(a);
        for(int i = 0; i<n;++i){
            int temp;
            scanf("%d",&temp);
            a[temp]++;
        }
        int ans = a[4];
        if(a[3]>=a[1]){//3 more than 1
            ans+=a[3];
            if(a[2] %2 == 0) ans+=a[2]/2;
            else ans+=a[2]/2+1;
        }else{// 1 more than 3
            ans+=a[3]; a[1]-=a[3];//1 3 组队
            if(a[2] %2 == 0){ans+=a[2]/2;a[2] = 0;}
            else{ans+=a[2]/2;a[2] = 1;}
            ans+=a[1]/4; a[1] = a[1] % 4;
            if((a[1] + a[2] * 2) % 4 == 0) ans+=(a[1] + a[2] * 2)/4;
            else ans+=(a[1] + a[2] * 2)/4 +1;
        }
        printf("%d\n",ans);
    }
    return 0;
}