Powers Of Two

题目大意

输入$n$和$k$，将$n$表示成 $k$ 个 $2^m$ 之和

Time: 4000 ms
Memory: 262144 kB

解题思路及分析

先将n分解成二的整数次幂之和，方法是和 1 2 4 8 等做 & 位运算
再依次把最大数分解成两个数，判断个数与k的关系
用优先队列维护

AC代码

#include <bits/stdc++.h>
using namespace std;

int main()
{
    vector<int> p2, ans;
    for (int i = 0; (1 << i) < 1e9; i++)
    {
        p2.push_back(1 << i);
    }
    int n, k;
    priority_queue<int> b;
    cin >> n >> k;
    for (int i = 0; i < p2.size(); i++)
    {
        int bi = n & p2[i];
        if (bi)
        {
            b.push(bi);
        }
    }
    while (b.size() < k)
    {
        int x = b.top();
        b.pop();
        b.push(x/2);
        b.push(x/2);
    }
    if (b.size() > k)
    {
        cout << "NO" << endl;
    }
    else
    {
        int sum = 0;
        while (!b.empty())
        {
            ans.push_back(b.top());
            sum += b.top();
            b.pop();
        }
        if (sum == n)
        {
            cout << "YES" << endl;
            for (int i = 0; i < ans.size(); i++)
            {
                cout << ans[i] << ' ';
            }
            cout << endl;
        }
        else 
        {
            cout << "NO" << endl;
        }
    }
    return 0;
}