蓝桥杯2021最少砝码

你有一架天平。现在你要设计一套砝码，使得利用这些砝码可以称出任意小于等于N的正整数重量。
那么这套砝码最少需要包含多少个砝码？
注意砝码可以放在天平两边

输入格式

输入包含T组测试数据，T不超过100。
每组测试数据输入一行包含一个正整数N，N不超过10^9。

输出格式

对于每组测试数据，输出一行表示答案。 

输入样例

2
7
15

输出样例

3
4 

新人第一次写题解，可能有些不清楚的地方，多包涵~ 先上代码

1.  
   #include <bits/stdc .h>
2.  
   using namespace std;
3.  
   int T, n, N;
4.  
   queue<int> r;
5.  
    
6.  
   int main() {
7.  
   cin >> T;
8.  
   n = T;
9.  
   for (int i = 1; i <= T; i ) {
10.  
    cin >> N;
11.  
    r.push(N);
12.  
    }
13.  
    if (n >= 1) {
14.  
    for (int j = 1; j <= T; j ) {
15.  
    long a = 1, b = 1, c = 1;//a是砝码个数，b是需要新增的砝码，c代表可以称出的重量
16.  
    while (c <= r.front()) {
17.  
    a ;
18.  
    b = b * 3;
19.  
    c = c b;
20.  
    }
21.  
    r.pop();
22.  
    r.push(a);
23.  
    }
24.  
    n = n - 1;
25.  
    }
26.  
    while (!r.empty()) {
27.  
    cout << r.front() << endl;
28.  
    r.pop();
29.  
    }
30.  
    return 0;
31.  
    }

那么从头开始解释起。

1.  
   int T, n, N;
2.  
   queue<int> r;

首先我定义了3个变量和一个队列，T是输入数据的数量，n后面用来判断执行多少次，N是输入的数据。定义了一个名为r的队列来储存。 

1.  
   cin >> T;
2.  
   n = T;
3.  
   for (int i = 1; i <= T; i ) {
4.  
   cin >> N;
5.  
   r.push(N);
6.  
   }

先输入有多少个数据，然后执行一个for循环。r.push() 是在队列尾部插入元素。

1.  
   if (n >= 1) {
2.  
   for (int j = 1; j <= T; j ) {
3.  
   long a = 1, b = 1, c = 1;//a是砝码个数，b是需要新增的砝码，c代表可以称出的重量
4.  
   while (c <= r.front()) {
5.  
   a ;
6.  
   b = b * 3;
7.  
   c = c b;
8.  
   }
9.  
   r.pop();
10.  
    r.push(a);
11.  
    }
12.  
    n = n - 1;
13.  
    }

 当需要称出重量为1的时候，需要1个重量为1的砝码，

当需要称出重量为2的时候，可以加一个重量为2的砝码，也可以加一个重量为3的砝码。但要求最少需要多少个砝码，所以我们单个砝码重量要尽可能的大，加一个重量为3的砝码，然后可以通过 3-1来称出重量为2。

需要称出5的时候，可以求得最大需要一个重量为9的砝码。由此可以发现一个规律：砝码的重量分别是1，3，9......，最大可称的重量是1，4，13......

那么可以推得：砝码数量 1，增加的那个砝码重量是前一个的3倍，前一个最大可称的重量加上增加砝码的重量就是当前可以称出来的最大重量，然后用可以称出的最大重量和给的数据N对比一下。

r.pop();  r.push();  在这边就是将已经完成的第一个元素移除，然后在队尾加上判断后的答案。

1.  
   while (!r.empty()) {
2.  
   cout << r.front() << endl;
3.  
   r.pop();
4.  
   }

最后输出结果就行。

这篇好文章是转载于：学新通技术网