#P7402. 二分的代价
二分的代价
题目描述
有一个长度为 的严格递增数组 ,以及一个与所有数组元素均不相等的数 。你要确定 应插入数组的哪个位置,保持数组递增。一共有 种可能的插入位置。
每次可以询问 与 的大小关系,代价为 。可以根据已有的询问结果决定下一次询问哪个位置,直到能确定插入位置。一个策略的代价是它在最坏情况下的询问代价之和。
给定 ,求所有策略中最小的最坏代价。
输入格式
输入一行,由 个数字组成。第 个数字是 ,数字之间没有空格。
输出格式
一行一个整数,表示答案。
样例
111
2
数据范围
,。
- 对于 的数据,所有 。
- 另有 的数据,。
- 另有 的数据,。