Description

计算机学院辅导员要求S10策划一次春游活动
学院有n 个同学，被分成m 个小组，每个小组的人数不超过4 人。
现在有一种汽车，每辆车最多坐4 人，可以不坐满，要求同一小组的同学必须坐在同一辆车上，而一辆车可以载上来自多个不同小组的同学。
问最少需要多少辆车，能够满足这次的春游计划。

Input

多组数据，第一行给出数据组数T （1≤T≤5000 ）
每组数据首先给出两个整数n 和m （1≤n,m≤1e5 ）
随后一行有m 个整数，a1,a2,a3...am 表示每个小组的人数。（1≤ai≤4 ）

Output

每一组数据输出一个整数，表示春游出行最少需要的车辆

Sample Input

2

10 4

1 2 3 4

7 4

1 2 2 2

Sample Output

3

2

题解：

我不确定对

思路没错应该

这题感觉n没啥子用

首先用a存储每种小组的个数

4人的小组必定不能与其他小组拼车

所以ans=a【4】

三人的小组可能可以与1人的拼车

二人的小组首先和二人的拼车

如果二人的有余（也就是一个小组）再与一人小组拼车

最后一人小组自己拼车

#include <iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
int t,n,m;
using namespace std;
long long  a[5],c,b[200000],sum;
int main()
{
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&m);
        a[1]=0;
        a[2]=0;
        a[3]=0;
        a[4]=0;
        for(int i=1;i<=m;i++){
             scanf("%lld",&sum);
            a[sum]++;
        }
        long long ans=a[4];
        ans+=a[3];
        if(a[3]<=a[1]){
            a[1]-=a[3];
        }else{
            a[1]=0;
        }
        ans+=a[2]/2;
        a[2]%=2;
        if(a[2]>0){
            ans++;
            if(a[1]>=2)
                a[1]-=2;
            else if(a[1]>0)
                a[1]--;
        }
        ans=ans+a[1]/4;
        if(a[1]%4)
		ans++ ;
		cout << ans << endl;
    }
    //cout << "Hello world!" << endl;
    return 0;
}

C++版本二

某一AC代码

思路是先排序，最后面的队肯定只用一次，然后从最前面加过来，加到超过4人位置，然后再变一下起止位置。

#include <iostream>
#include <stdio.h>
#include <string.h>
#include  <queue>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <vector>
#include <stack>//栈，先进先出
using namespace std;
int a[100000];
int main(int argc, char *argv[])
{
    int t,n,m;//n是人数，m是组数
    cin>>t;
    while(t--)
    {
        int car=0;
        int head,rear;
        cin>>n>>m;
        head=0;
        rear=m-1;
        for(int i=0; i<m; i++)
        {
            scanf("%d",&a[i]);
        }
        sort(a,a+m);
        for(int i=head; i<=rear;)
        {
            int cn=i;
            int total=a[rear];
            if(head==rear)
            {
                car++;
                break;
            }
            while(1)
            {

                if(total+a[cn]<=4)
                {
                    total=a[rear]+a[cn];
                    cn+=1;
                }
                else
                {

                    car++;
                    rear--;
                    head=cn;
                    i=head;
                    break;
                }
            }
        }
        cout<<car<<endl;
    }

return 0;
}