题解：AT_dwango2017qual_c スキーリフトの相乗り

由于每个人都要上车，改变顺序时最优答案不变，所以可以不考虑顺序。

要想车数量最少，那么每辆车就要尽可能利用，也就是要坐最多人。

由于每队人数最多为四，最少为一，故可以统计每种人数的队伍数量，记为

a1

，

a2

，

a3

，

a4

。

分别考虑：

$a4$ ：单独一队一车，共 $a4$ 辆车。
$a3$ ：尽可能和 $a1$ 拼，要是 $a1$ 不够，那么单独一队一车，共 $a3$ 辆车。 $a1$ 消掉 $\min(a3,a1)$ 。
$a2$ ：先尽量两个两个拼，如果有多余一队，那么和 $a1$ 拼。共 $\lceil a2\div 2\rceil$ 辆车， $a1$ 消掉 $\min(a[1],2)$ 。
$a1$ ：由于前面的队伍都拼完了，所以只能自己拼，共 $\lceil a1\div 4 \rceil$ 辆车。

code

CPP

#include<bits/stdc++.h>
using namespace std;
int a[5];
int main(){
	int n;
	cin>>n;
	for(int i=0;i<n;i++){
		int x;
		cin>>x;
		a[x]++;
	}
	int ans=a[4];
	ans+=a[3];
	a[1]-=min(a[3],a[1]);
	ans+=a[2]/2;
	if(a[2]%2){
		ans++;
		if(a[1]>=1){
			a[1]-=min(a[1],2);
		}
	}
	ans+=(a[1]+3)/4;
	cout<<ans<<endl;
}

题解：AT_dwango2017qual_c スキーリフトの相乗り

文章操作

code

相关推荐

评论

题解：AT_dwango2017qual_c スキーリフトの相乗り