2020牛客暑期多校训练营（第七场） 题解

• B - Mask Allocation

牛客多校，第七场。

若有公式图片无法正常显示，请使用梯子访问！

B - Mask Allocation

• 题意:
  给定n*m个物品，要求构造出k堆物品，并使这些堆可以任意组合为n堆m个物品与m堆n个物品，求最小的k以及对应方案。

  样例1解释：
  输入
  5 4
  输出
  8
  4 4 4 4 1 1 1 1
  n堆m个物品：(4),(4),(4),(4),(1+1+1+1)
  m堆n个物品：(4+1),(4+1),(4+1),(4+1)

• 思路:
  贪心构造即可。迭代依次构造较小的数的平方，再依次减即可。

  例如：
  输入 n=13 m=5 时：

  1. 较小数=5，构造5*5:
     ans={5,5,5,5,5}, 剩余m=8, n=5

  2. 较小数=5, 构造5*5:
     ans={5,5,5,5,5,5,5,5,5,5}, 剩余m=3, n=5

  3. 较小数=3, 构造3*3:
     ans={5,5,5,5,5,5,5,5,5,5,3,3,3},剩余m=3, n=2

  4. 较小数=2, 构造2*2:
     ans={5,5,5,5,5,5,5,5,5,5,3,3,3,2,2},剩余m=1, n=2

  5. 较小数=1，构造1*1:
     ans={5,5,5,5,5,5,5,5,5,5,3,3,3,2,2,1},剩余m=1, n=1

  6. 现在m=1,n=1,最后补一个1即可。

  如上，即为贪心最优解思路。

int main()
{
    IOS;
    int T;
    cin >> T;
    while (T--)
    {
        int n, m;
        cin >> n >> m;
        if (n < m) //默认n>m
            swap(n, m);
        vector<int> ans;
        while (1)
        {
            for (int i = 0; i < m; i++) // 构造较小物品
                ans.push_back(m);
            n -= m; 
            if(n*m==0) //当没有物品可以构造
            break;
            if (n < m) //默认n>m
                swap(n, m);
        }
        cout << ans.size() << endl;
        for (int i = 0; i < ans.size(); i++)
            cout << ans[i] << " ";
        cout << endl;
    }
    return 0;
}