大意: 求将n划分为k个2的幂的和, 且最大幂最小,字典序尽量大
比较简单的贪心练习题, 但放在div2的B题感觉偏难了.....
先只考虑最大幂最小, 首先注意到直接按n的二进制划分即可得到最小划分, 所以若k小于n二进制中1的个数的话显然不存在方案
否则若k足够大的话, 要使最高幂最小, 可以把最高幂可以分解成两个低次幂, 这样会使划分数增加1
基本思想就是用贪心从最坏状态调整到最优状态, 由于每次划分数加1, 一定可以达到k划分
但是这样划分完, 可以发现得到的划分字典序一定是最小的, 为了使字典序最大, 再进一步调整
假设最大幂最$mx$, 每次选出第一个小于$mx$的数$x$, 将2个$x$转化为$x+1$ (其实这里x只能是mx-1)
为了使划分数不变, 再选出最小的数$y$, 将$y$转化为2个$y-1$即可
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <map>
#define REP(i,a,n) for(int i=a;i<=n;++i)
using namespace std;
typedef long long ll; const int N = 4e5+10;
ll n;
int k; int main() {
scanf("%lld%d", &n, &k);
map<int,int,greater<int> > s;
int sz = 0;
REP(i,0,61) if (n>>i&1) ++s[i],++sz;
if (sz>k) return puts("NO"),0;
puts("Yes");
while (sz!=k) {
auto t = s.begin();
int num = t->first;
if (!--s[num]) s.erase(t);
s[num-1] += 2;
++sz;
}
int mx = s.begin()->first;
while (s[mx-1]>=2) {
if (s[mx-1]==2&&s.upper_bound(mx-1)==s.end()) break;
if (!(s[mx-1]-=2)) s.erase(mx-1);
++s[mx];
auto t = s.end(); --t;
int num = t->first;
if (!--s[num]) s.erase(t);
s[num-1] += 2;
}
for (auto t:s) REP(i,1,t.second) printf("%d ",t.first);
puts("");
}