caioj 2015: Tyb的征途计划
题目描述
背景：
tybAU后开始胡思乱想。
题目描述：
一天，tyb带领着他的骑士团开始征服世界了！
Tyb所在的世界比较奇怪，城市与城市间的有向道路形成一个以1为根，有n个点的完全二叉树。即城市i有通向2*i与2*i+1城市的路。
Tyb的一次征途是这样的：他可以瞬移到任何一个城市，招兵买马，然后沿着道路将沿途的城市征服。因为tyb战无不胜，以德服人，所以绝不会重复到一个点。
现在tyb想知道，它最少征战多少次才能征服世界。
一句话题意：求一个有n个点的完全二叉树的最小路径覆盖。
输入描述：
一个数n，表示城市数.
输出描述：
一个数ans，即tyb最少征途数。
样例输入：
7
样例输出：
4
题解
这题就是找这棵树叶子节点的个数
FYC说他推了一个公式:ans=(n-1)/2+1
FYC说证明显然，就不告诉你们了
就这样吧。。
CODE：
由于是直接在提交页面写的，于是没有排版
#include本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！