B-Mask Allocation
Mask Allocation
https://ac.nowcoder.com/acm/contest/5672/B
链接：https://ac.nowcoder.com/acm/contest/5672/B
来源：牛客网
题意：
给你n * m个口罩，让你将口罩进行分组装箱，使其满足给n个医院，每个医院分配m个口罩，及m个医院，每个医院分配n个口罩，要求分的组数尽可能少，并且字典序最大
solution：
对n和m进行gcd递归求解
举个例子：17 5
gcd(17,5)->17/55=15,可以5个口罩装箱，装15个箱子，然后gcd(5,2),同理,5/22=2，4个箱子装有两个口罩，gcd(2,1)，2/1*1=2,两个箱子装一个口罩，gcd(1,0)退出递归，这样递归求解，就能构造出最优解
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int t,n,m;
int cnt[10005];
int res;
void gcd(int a,int b)
{
if(b==0)return;
int num=a/b*b;
cnt[b]=num;
res+=num;
gcd(b,a%b);
}
int main()
{
cin>>t;
while(t--)
{
cin>>n>>m;
res=0;
memset(cnt,0,sizeof(cnt));
gcd(n,m);
printf("%d\n",res);
for(int i=max(n,m);i>=0;i--)
{
for(int j=0;j<cnt[i];j++)
printf("%d ",i);
}
printf("\n");
}
return 0;
}
上次被挂了后我连简历都不刷了
查看30道真题和解析