题解 | #称砝码#

题意

有n种数，第i种数有a_i个，求取得的数的总和的数量。

分析

问题可以转化为两步： 1.存储所有不同选数方案的总和。2. 对总和去重并算出总和数目。

我们可以考虑使用C++语言中自带的STL容器set，利用set存储所得答案并去重。

#include<bits/stdc++.h>
using namespace std;
set <int> ans,p;
int n,m[11][2];
int main()
{
    while(~scanf("%d",&n))//读取砝码数量
    {
        ans.clear();//对答案集合初始化
        for(int i=1;i<=n;i++) cin >> m[i][0];
        for(int i=1;i<=n;i++) cin >> m[i][1];//读入砝码个数
        vector<int> tmp;
        tmp.clear();
        for(int i=1;i<=n;i++)
        {
            while(m[i][1]--)
            {
                tmp.push_back(m[i][0]);//在tmp中存入砝码质量
            }
        }
        ans.insert(0);//初始没有砝码只能称出0
        for(auto it=tmp.begin();it!=tmp.end();it++)//对tmp进行遍历
        {
            //const auto END=ans.end();
            p=ans;
            for(auto itt=p.begin();itt!=p.end();itt++) ans.insert(*it+*itt);
            //对于每一个ans中原有数量值，将其加上当前砝码质量并存入ans
        }
        cout << ans.size() <<endl;//答案为ans set内元素个数
    }

}

例如，对于这样的一组数据，用1，1，3，3四个砝码已经能表示以下几种质量，则加上砝码后可以表示下一行的这几个质量，将上下两行合并去重即可。

这样一直到最后一个砝码，我们就可以求出所有可能的表示重量。

时间复杂度:$O(nQ)O(nQ)$,其中$QQ$是数据组数。

空间复杂度:$O(nMX)O(nMX)$,其中$M=max(m_1,m_2,\mathrm{.}\mathrm{.}\mathrm{.},m_n)M=max(m\_1,m\_2,...,m\_n)$,$X=max(x_1,x_2,\mathrm{.}\mathrm{.}\mathrm{.},x_n)X=max(x\_1,x\_2,...,x\_n)$，为存储砝码与答案用的ans集合的空间。