当前位置：首页 > article >正文

蓝桥杯12届砝码称重

article 2025/3/24 17:02:49

问题描述

你有一架天平和 N 个砝码，这 N 个砝码重量依次是 W1,W2,⋅⋅⋅,WN。

请你计算一共可以称出多少种不同的重量？注意砝码可以放在天平两边。

输入格式

输入的第一行包含一个整数 N。

第二行包含 N 个整数：W1,W2,W3,⋅⋅⋅,WN。

输出格式

输出一个整数代表答案。

样例输入

3
1 4 6

样例输出

样例说明

能称出的 10 种重量是：1、2、3、4、5、6、7、9、10、11。

1=1；

2=6−4(天平一边放 6，另一边放 4)；

3=4−1；

4=4；

5=6−1；

6=6；

7=1+6；

9=4+6−1；

10=4+6；

11=1+4+6。

评测用例规模与约定

对于 50的评测用例，1≤N≤15。

对于所有评测用例，1≤N≤100,N个砝码总重不超过 100000。

迭代器的作用

s.begin()：返回指向集合 s 第一个元素的迭代器。

s.end()：返回指向集合 s 末尾的迭代器（最后一个元素的下一个位置）。

范围 [s.begin(), s.end())：包含集合 s 的所有元素。

#include<iostream>
#include<set>
#include<vector>
#include<cmath>
using namespace std;

int n;
typedef long long ll;
ll ans;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin>>n;
	set<int> s;
	for(int i=1; i<=n; ++i)
	{		
		int w;
		cin>>w;
		
		//v:临时存储当前已计算出的所有可能重量值 
		vector<int> v(s.begin(), s.end()); 
		//这里调用了vector的范围构造函数，其功能是将s的所有元素复制到v中
		
		for(int j=0; j<v.size(); ++j)
		{ 
		    //v[j]是天平显示的重量 
			s.insert(abs(w+v[j]));  //加上当前的砝码 
			s.insert(abs(w-v[j]));  //减去当前的砝码 
		}
		//w本身也要插入到s里 
		s.insert(w);
	} 
	//若s中有0，删除0 
	if(s.count(0)) s.erase(0);
	
	cout<<s.size();
	
	return 0;
}

以下是输入 n=3 和砝码 1, 4, 6 时程序的详细运行过程：

初始化

n = 3
集合 s 初始为空：s = {}

处理第一个砝码 `w=1`

复制当前 s 到 v：
v = {}（空向量）。
遍历 v：
v 为空，循环不执行。
插入 w=1：
s = {1}。

处理第二个砝码 `w=4`

复制当前 s 到 v：
v = {1}。
遍历 v：
- v[0] = 1：
  - 1 + 4 = 5 → s.insert(5) → s = {1, 5}。
  - |1 - 4| = 3 → s.insert(3) → s = {1, 3, 5}。
插入 w=4：
s.insert(4) → s = {1, 3, 4, 5}。

处理第三个砝码 `w=6`

复制当前 s 到 v：
v = {1, 3, 4, 5}。
遍历 v：
- v[0] = 1：
  - 1 + 6 = 7 → s.insert(7) → s = {1, 3, 4, 5, 7}。
  - |1 - 6| = 5 → 5 已存在，s 不变。
- v[1] = 3：
  - 3 + 6 = 9 → s.insert(9) → s = {1, 3, 4, 5, 7, 9}。
  - |3 - 6| = 3 → 3 已存在，s 不变。
- v[2] = 4：
  - 4 + 6 = 10 → s.insert(10) → s = {1, 3, 4, 5, 7, 9, 10}。
  - |4 - 6| = 2 → s.insert(2) → s = {1, 2, 3, 4, 5, 7, 9, 10}。
- v[3] = 5：
  - 5 + 6 = 11 → s.insert(11) → s = {1, 2, 3, 4, 5, 7, 9, 10, 11}。
  - |5 - 6| = 1 → 1 已存在，s 不变。
插入 w=6：
s.insert(6) → s = {1, 2, 3, 4, 5, 6, 7, 9, 10, 11}。