2020牛客暑期多校训练营(第七场)B.Mask Allocation(构造)
地址:https://ac.nowcoder.com/acm/contest/5672/B
题意:
给出n*m个口罩,把它们分成k组,可以取:n组,每组m个口罩,m组,每组n个口罩
求最小k,并按字典序从大到小输出
解析:
来自:https://www.cnblogs.com/xyq0220/p/13418260.html 的解释。
规定n<m
#include<bits/stdc++.h> #include<iostream> #include<cstring> #include<string.h> #include<cmath> #include<vector> #include<map> using namespace std; typedef long long ll; const int maxn=1e5+20; int a[maxn]; int main() { int t; scanf("%d",&t); while(t--) { int n,m; cin>>n>>m; vector<int>v; while(n&&m) { if(n>m) swap(n,m); for(int i=1;i<=n;i++) v.push_back(n); m-=n; } cout<<v.size()<<endl; for(int i=0;i<v.size();i++) { cout<<v[i]<<" "; } cout<<endl; } }