题目描述

Description

在byteotian公司搬家的时候，他们发现他们的大量的精密砝码的搬运是一件恼人的工作。公司有一些固定容
量的容器可以装这些砝码。他们想装尽量多的砝码以便搬运，并且丢弃剩下的砝码。每个容器可以装的砝码数量有
限制，但是他们能够装的总重量不能超过每个容器的限制。一个容器也可以不装任何东西。任何两个砝码都有一个
特征，他们的中总有一个的重量是另外一个的整数倍，当然他们也可能相等。

Input

第一行包含两个数n和m。表示容器的数量以及砝码的数量。(1<=n, m<=100000) 第二行包含n个整数wi，表示
每个容器能够装的最大质量。(1<=wi<=1000000000) 第三行包含m个整数mj，表示每个砝码的质量。(1<=mj<=10000
00000)

Output

仅包含一个数，为能够装进容器的最多的砝码数量。

Sample Input

2 4
13 9
4 12 2 4

Sample Output

3

题目分析

比较强的贪心
注意到< 总有一个的重量是另外一个的整数倍 >这个性质 我们把所有的a[]分解成b[]的倍数的形式 优先分解最大的b[]
贪心策略：能装小的肯定先装小的
那我们就从小到大枚举b[] 如果能装就装 不能装看看能不能从高位借位

#include <cstdio>
#include <cstring>
#include <set>
#include <map>
#include <vector>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int n,m,cnt,dx=1;
int a[100100],b[100100],c[200],d[100100];
int can()
{
    for(int i=dx+1;dx<=cnt;dx++)
        if(d[i]>0)
        {
            d[i]--,d[dx]+=c[i]/c[dx];
            return 1;
        }
    return 0;
}
int main()
{   
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=m;i++) scanf("%d",&b[i]);
    sort(b+1,b+m+1);
    for(int i=1;i<=m;i++) if(b[i]!=b[i-1]) c[++cnt]=b[i];
    for(int i=cnt;i>=1;i--)
        for(int j=1;j<=n;j++) d[i]+=a[j]/c[i],a[j]%=c[i];
    for(int i=1;i<=m;i++)
    {
        while(c[dx]<b[i]) dx++;
        if(d[dx]) d[dx]--;
        else if(can()) d[dx]--;
        else
        {
            printf("%d",i-1);
            return 0;
        }
    }
    printf("%d",m);
    return 0;
}