Решение задачи "Степени двойки" с Codeforces

С пояснением Просмотров: 29

Положительное целое число x называется степенью двойки, если его можно представить как x=2y, где y — неотрицательное целое число. Иными словами, степени двойки — это числа 1,2,4,8,16,….

Вам даны два положительных целых числа n и k. Представьте n как сумму ровно k степеней двойки.

#include<bits/stdc++.h>

using namespace std;

int main()
{
	int n, k;
	cin >> n >> k;
	map<int, int> ans;
	queue<int> q;
	for(int i = 0; i <= 30; i++)
		if(n & (1 << i))
		{
			if(i > 0) q.push(1 << i);
			ans[1 << i]++;
		}
	if(int(ans.size()) > k)
	{
		puts("NO");
		return 0;
	}
	int cnt = ans.size();
	while(cnt < k && !q.empty())
	{
		int z = q.front();
		q.pop();
		ans[z]--;
		ans[z / 2] += 2;
		if(z / 2 > 1)
		{
			q.push(z / 2);
			q.push(z / 2);
		}
		cnt++;
	}
	if(cnt < k)
	{
		puts("NO");
		return 0;
	}
	puts("YES");
	for(auto x : ans)
		for(int i = 0; i < x.second; i++)
			printf("%d ", x.first);
	puts("");
	return 0;
}

Сначала давайте поймем, как мы можем получить минимальное количество степеней двойки, необходимых для того, чтобы представить n в виде их суммы. Мы можем воспользоваться двоичным представлением n: каждый бит в нем, равный 1, добавляет в ответ одно слагаемое.

Сначала, если количество слагаемых больше, чем k, то ответ NO. Окей, что нужно делать, если нам не хватает слагаемых? Каждое слагаемое x>1 может быть разбито на два слагаемых, равных x2. Давайте сохраним все слагаемые больше 1 где-нибудь (стек, массив, очередь, мультимножество, где вы хотите), будем выбирать любое слагаемое и разбивать его на два до тех пор, пока у нас не станет ровно k слагаемых. Если n≥k, то этот процесс точно когда-то закончится, потому что всегда найдется какое-то слагаемое для выбора до тех пор, пока они все не станут равны 1.