Codeforces 1348 D. Phoenix and Science

   日期:2020-05-05     浏览:112    评论:0    
核心提示:题意:第一天有一个细胞质量为 111 ,每一天白天细胞可以发生分裂,晚上细胞质量增加。给定一个 nn

题意:

第一天有一个细胞质量为 1 1 1 ,每一天白天细胞可以发生分裂,晚上细胞质量增加。给定一个 n n n ,问至少要多少天,细胞总质量恰好达到为 n n n

先考虑分裂,分裂不会对细胞的总质量带来任何影响,只是会影响晚上细胞质量增加的值。若当前细胞数量为 x x x,那么晚上细胞可以增加的质量 d m dm dm 满足 x ≤ d m ≤ 2 x x≤dm≤2x xdm2x

可以确定的是细胞增加最快的情况是:每一天白天所有细胞都发生分裂。但是这样不能保证最后细胞总质量恰好达到 n n n

计算 x x x 为满足的最大值 n ≥ 2 0 + 2 1 + . . . + 2 x n≥2^0+2^1+...+2^x n20+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 nsum插入增加的队列。排序。

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;
}
 
打赏
 本文转载自:网络 
所有权利归属于原作者,如文章来源标示错误或侵犯了您的权利请联系微信13520258486
更多>最近资讯中心
更多>最新资讯中心
0相关评论

推荐图文
推荐资讯中心
点击排行
最新信息
新手指南
采购商服务
供应商服务
交易安全
关注我们
手机网站:
新浪微博:
微信关注:

13520258486

周一至周五 9:00-18:00
(其他时间联系在线客服)

24小时在线客服