c++超导材料问题！

Question

科学家发现了一种神奇的材料，当其质量为 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

Answer 1

#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;
}