题意:
第一天有一个细胞质量为 1 1 1 ,每一天白天细胞可以发生分裂,晚上细胞质量增加。给定一个 n n n ,问至少要多少天,细胞总质量恰好达到为 n n n。
先考虑分裂,分裂不会对细胞的总质量带来任何影响,只是会影响晚上细胞质量增加的值。若当前细胞数量为 x x x,那么晚上细胞可以增加的质量 d m dm dm 满足 x ≤ d m ≤ 2 x x≤dm≤2x x≤dm≤2x。
可以确定的是细胞增加最快的情况是:每一天白天所有细胞都发生分裂。但是这样不能保证最后细胞总质量恰好达到 n n n。
计算 x x x 为满足的最大值 n ≥ 2 0 + 2 1 + . . . + 2 x n≥2^0+2^1+...+2^x n≥20+21+...+2x ,令 s u m = 2 0 + 2 1 + . . . + 2 x sum=2^0+2^1+...+2^x sum=20+21+...+2x,若 s u m = = n sum==n sum==n,那么每天全部分裂即可。否则将 n − s u m n-sum n−sum插入增加的队列。排序。
AC代码:
ll n;
int t;
int main()
{
int t;
sd(t);
while (t--)
{
sld(n);
vector<ll> v;
ll sum = 0;
for (int i = 1; sum + i <= n; i *= 2)
{
sum += i;
v.pb(i);
}
if (sum < n)
v.pb(n - sum);
sort(v.begin(), v.end());
int len = v.size();
pd(len - 1);
rep(i, 1, len - 1)
{
printf("%lld%c",v[i] - v[i - 1],i==len-1?'\n':' ');
}
printf("\n");
}
return 0;
}