称砝码【set】

称砝码_牛客题霸_牛客网 (nowcoder.com)

题目大意描述

当前有n个砝码，给你每个砝码的重量和数量，计算出这些砝码可以称哪些重量（不同重量数）

解决代码

#include
#include
#include
using namespace std;

const int MAX_NUM = 10;

int n , num[MAX_NUM] ;
vector<int> weightNums ;
set<int> ans;

void input(){
    cin >> n;
    for(int i = 0 ; i < n ; i  ++){
        cin >> num[i];
    }
    int temp ;
    for(int i = 0 ; i < n ; i ++){
        cin >> temp;
        for(int j = 0 ; j < temp ; j ++){
            weightNums.push_back(num[i]);
        }
    }
}

void deal(){
    ans.insert(0);
    int len = weightNums.size();
    for(int i = 0 ;i < len ; i ++){
        set<int> temp(ans);
        for(auto x : temp){
            ans.insert(x + weightNums[i]);
        }
    }
}

void output(){
    cout << ans.size();
}

int main(){
    input();
    deal();
    output();
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

代码解释

输入——vector替代map思路

首先第一个值得解释的点就是输入。

因为题目中给出的砝码的个数和重量是匹配的，即按照重量输入顺序给出对应的数量

我们可以利用这个条件，对空间进行节省

一般操作

一般情况，我们可能会采用这样的方式分开存储数据

for(int i = 0 ; i < n ; i ++){
	cin >> weight[i];
}
for(int i = 0 ; i < n ; i ++){
	cin >> num[i]
}
1
2
3
4
5
6

这样将会要

• 浪费空间——两个数组空间
• 割裂关系——两个分开的数组导致两者之间的关系分离，不清楚关系

神之一手

基于上面的问题，我们可以对代码进行以下优化

for(int i = 0 ; i < n ; i ++){
	cin >> num[i]
}
for(int i = 0 ; i < n ; i ++){
	cin >>temp;
	for(int j = 0 ; j < temp ; j ++){
		vec.push_back(num[i]);
	}
}
1
2
3
4
5
6
7
8
9

• 对于第一个循环输入不变

• 对于第二个循环，无需数组去装载数量

  既然第二个输入的是数量，也就是说重复当前个数的重量

  而且个数在当前是无用的，根本无需占用一个数组空间去存储

• 在第二个循环内增加一个循环，将真正的数据放入一个vector中

  当然这里看起来是多出了一个循环，并且空间也并没有因此得到减少

  但是增强了彼此的联系，在输入的过程中就将所有真实的数据放入同一个位置，便于后续操作

  而且真正需要用到的就只有一个vector的变量，num只需要在input 函数中作为局部变量即可——简化代码变量逻辑

处理逻辑

这个处理逻辑才是最妙的，当时看到这个代码的时候愣住了，真正明白自己写出来的时候，惊为天人！！！

这里的称砝码就相当于一次全排列，只是需要删除重复的和

中间最难的一个点就是，我们要怎么样才能把各个和加起来，并且还不出现重复

这里的解决办法就是：利用set

逻辑梳理

首先我们将问题在自己的纸上复现一遍，人工求出答案。

就不难发现，首先默认的cnt为1——因为0也算进去

然后，我们对数字进行遍历

• 0
• 0 + 1 = 1
• 1 + 1 = 2
• 2(1+1) + 2 = 4
• 1 + 2 = 3

首先初始中有0，我们将vector中的数据1

第二步，我们拿到第二个vector中的数字——1，去遍历set中的数据

得到结果0 1 1 2，由于set的去重，得到结果0 1 2

……

复现下来，我们发现我们去寻找的时候的操作如下

• 遍历vector中的数据——x
• 在拿到vector数据（x）后，将set中所有的数据都加上（x），并插入set中

最后形成代码

ans.insert(0);
for(int i = 1 ; i < vector长度 ; i ++){
	set<int> temp(ans);
	for(auto x : temp){
		ans.insert(x + vector数据[i]);
	}
}
1
2
3
4
5
6
7

需要注意的一个点

这里需要用temp临时变量去操作，因为在set进行insert操作时，会改变其长度，导致死循环

输出

最后输出set的大小即可。