B. Taxi （贪心）

dejavu1zz

发布于 2020-10-23 15:16:36

3910

发布于 2020-10-23 15:16:36

文章被收录于专栏：奇妙的算法世界

原题链接

158B

题目描述

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 si friends (1 ≤ si ≤ 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

The first line contains integer n (1 ≤ n ≤ 105) — the number of groups of schoolchildren. The second line contains a sequence of integers s1, s2, …, sn (1 ≤ si ≤ 4). The integers are separated by a space, si is the number of children in the i-th group.

Output

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

inputCopy 5 1 2 4 3 3 outputCopy 4 inputCopy 8 2 3 4 4 2 1 3 1 outputCopy 5

思路

一道贪心的题目，刚开始看错了题，后来才发现一辆车必须载整个组的人。由于每组人数至多4人，所以我们可以维护一个cnt数组，记录每组人数的数量。题目要求求出最少的车辆，我们的策略就是：四人组的无法与其他组同坐，三人组的可以与一人组同坐，二人组可以和二人组同坐，四个一人组可以在一起，做完这些后再处理剩余的二人组和一人组，每个二人组可以与两个人一组同坐，最后再处理一遍一人组即可。

AC代码

#include<bits/stdc++.h>
#define x first
#define y second
#pragma GCC optimize(2)
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC optimize(3)
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC target("sse3","sse2","sse")
#pragma GCC target("avx","sse4","sse4.1","sse4.2","ssse3")
#pragma GCC target("f16c")
#pragma GCC optimize("inline","fast-math","unroll-loops","no-stack-protector")
#pragma GCC diagnostic error "-fwhole-program"
#pragma GCC diagnostic error "-fcse-skip-blocks"
#pragma GCC diagnostic error "-funsafe-loop-optimizations"
#pragma GCC diagnostic error "-std=c++14"
#define IOS ios::sync_with_stdio(false);cin.tie(0);
using namespace std;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
typedef long long LL;
const int N=1e5+10;
const int INF=0x3f3f3f3f;
const int MOD=998244353;
int n;
int a[N];
int cnt[5];
int main(){
	IOS;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
        cnt[a[i]]++;
    }
    int ans=0;
    ans+=cnt[4];
    ans+=cnt[3];
    cnt[1]-=cnt[3];
    if(cnt[1]<=0) ans+=cnt[2]/2+cnt[2]%2;
    else{
        ans+=cnt[1]/4;
        cnt[1]-=cnt[1]/4*4;
        ans+=cnt[2]/2;
        cnt[2]-=cnt[2]/2*2;
        ans+=cnt[2];
        cnt[1]-=cnt[2]*2;
        if(cnt[1]>0) ans+=1;
    }
    cout<<ans<<endl;
	return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2020/04/03 ，如有侵权请联系 cloudcommunity@tencent.com 删除

children