Codeforces Round #457 (Div. 2) B. Jamie and Binary Sequence(二进制，思路，贪心)

本文主要是介绍Codeforces Round #457 (Div. 2) B. Jamie and Binary Sequence(二进制，思路，贪心)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

描述

Jamie is preparing a Codeforces round. He has got an idea for a
problem, but does not know how to solve it. Help him write a solution
to the following problem:

Find k integers such that the sum of two to the power of each number
equals to the number n and the largest integer in the answer is as
small as possible. As there may be multiple answers, you are asked to
output the lexicographically largest one.

To be more clear, consider all integer sequence with length k
(a1, a2, …, ak) with . Give a value to each sequence. Among all
sequence(s) that have the minimum y value, output the one that is the
lexicographically largest.

For definitions of powers and lexicographical order see notes.

Input

The first line consists of two integers n and k
(1 ≤ n ≤ 1018, 1 ≤ k ≤ 105) — the required sum and the length of the
sequence.

Output

Output “No” (without quotes) in a single line if there does not exist
such sequence. Otherwise, output “Yes” (without quotes) in the first
line, and k numbers separated by space in the second line — the
required sequence.

It is guaranteed that the integers in the answer sequence fit the
range [ - 1018, 1018].

input

23 5

output

Yes
3 3 2 1 0

input

13 2

output

No

input

1 2

output

Yes
-1 -1

Note

Sample 1:

23 + 23 + 22 + 21 + 20 = 8 + 8 + 4 + 2 + 1 = 23

Answers like (3, 3, 2, 0, 1) or (0, 1, 2, 3, 3) are not
lexicographically largest.

Answers like (4, 1, 1, 1, 0) do not have the minimum y value.

Sample 2:

It can be shown there does not exist a sequence with length 2.

Sample 3:

Powers of 2:

If x > 0, then 2x = 2·2·2·…·2 (x times).

If x = 0, then 2x = 1.

If x < 0, then .

Lexicographical order:

Given two different sequences of the same length, (a1, a2, … , ak)
and (b1, b2, … , bk), the first one is smaller than the second one
for the lexicographical order, if and only if ai < bi, for the first i
where ai and bi differ.

思路

首先说题意，题目给了两个数 $n$ 和 $k$ ,把 $n$ 拆成k个2的次幂相加的形式，并且把次幂输出

要求：

满足k个2的次幂相加
最高位次幂要最小
按照字典序排列

拆的方法是：

2 n + 2 n = 2 * 2 n = 2 n + 1

$2^n+2^n=2*2^n=2^{n+1}$

假设现在有一组样例：1 7

那么首先，1的二进制形式是:1

把1拆成两个-1
把两个-1拆成4个-2
当把4个-2拆成8个-2时发现，要求只有7个，那么我们就不拆，把4个-2中最后面的-2拆成两个-3，把两个-3后面的-3拆成两个-4，两个-4后面的-4拆成两个-5，到此现在有7个了，停止，答案输出为:-2 -2 -2 -3 -4 -5 -5

代码

#include<bits/stdc++.h>
using namespace std;
long long n,k;
int a[100200],*cnt=a+100000;
int main()
{cin>>n>>k;for (int i=0; i<60; i++){cnt[i]+=n>>i&1;k-=cnt[i];}//用k统计一下还剩下多少位if (k<0){puts("No");return 0;}for (int i=59; i>=-60; i--)if (k>=cnt[i]){k-=cnt[i];cnt[i-1]+=2*cnt[i];//2*2^n=2^(n+1)cnt[i]=0;}else{int Min=-60;while (!cnt[Min])//找到最右边最小的一位Min++;while (k--){cnt[Min]--;cnt[--Min]+=2;}break;}puts("Yes");for (int i=59; i>=-100000; i--)while (cnt[i]--) printf("%d ",i);puts("");return 0;
}