科学家发现了一种神奇的材料，当其质量为 2 的幂时具有超导性
科学家制备了 n 份这种材料的样品，第 i 份样品的质量为 2 a i
为了得到质量更大的样品，可以把多份样品合并，这样得到的新样品的质量为 被合并的所有样品的质量之和
现在允许进行任意次合并，科学家希望最终得到的每一份样品都具有超导性。请问最终最少有多少份样品？
输入描述
第一行一个正整数 n
第二行 n 个数，表示 a i
输出描述
一行一个整数，表示最少得到多少份超导样品
用例输入 1
5
2 1 1 3 3
用例输出 1
2
提示
样例1解释
样品的质量分别依次为
2 ^2
2 ^1
2 ^1
2 ^3
2 ^3
，前 3 份样品可以合并为一份质量为 8 的样品，后 2 份可以合并为一份质量为 16 的样品。因此最少得到 2 份样品
数据范围
对于 20% 的数据，n≤10
对于 60% 的数据，n≤10000
对于 100% 的数据，1≤n≤10^6,0≤a i≤10 ^6
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> a(n);
for(int i = 0; i < n; i++) {
cin >> a[i];
}
sort(a.begin(), a.end());
int ans = 0;
for(int i = 0; i < n; ) {
if((a[i] & (a[i]-1)) == 0) { // 当前样品质量是2的幂
ans++;
i++;
} else {
int j = i-1;
while(j >= 0) {
if((a[i] + a[j]) & (a[i] + a[j] - 1) == 0) { // 找到可以合并的
i++;
break;
}
j--;
}
}
}
cout << ans << endl;
return 0;
}
【以下回答由 GPT 生成】
首先，我们需要将输入的样品质量从小到大进行排序，这样方便我们选择合并样品进行计算。然后，我们需要找到可以合并的样品中质量最小的一份，将其与质量次小的一份进行合并。将合并后的样品质量更新，再次排序。重复这个过程，直到无法继续合并为止。最终，剩余的样品数量即为最少得到的超导样品的数量。
具体的算法步骤如下：
读取样品数量n和每份样品的质量列表。
排序样品质量
对样品质量列表进行排序，从小到大。
合并样品
当样品数量等于1时，结束合并过程。
输出结果
下面是一个实现了上述算法的Python代码段：
n = int(input()) # 读取样品数量n
weights = list(map(int, input().split())) # 读取每份样品的质量列表
weights.sort() # 排序样品质量
count = 0 # 初始化计数器为0
while len(weights) > 1: # 当样品数量大于1时进行合并操作
min_weight1 = weights[0] # 找到质量最小的样品
min_weight2 = weights[1] # 找到次小的样品
weights.append(min_weight1 + min_weight2) # 添加合并后的样品质量到列表末尾
weights = weights[2:] # 删除原来的两份样品
count += 1 # 计数器递增
weights.sort() # 对样品列表重新排序
print(count) # 输出最少得到的超导样品的数量
这个算法的时间复杂度为O(nlogn)，其中n是样品数量。
【相关推荐】