链接: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; }