#P7402. 二分的代价

    ID: 7416 传统题 1000ms 256MiB 尝试: 2 已通过: 2 难度: 8 上传者: 标签>CF2500提高+/省选-以值为状态状态维度消除消除被支配候选

二分的代价

题目描述

有一个长度为 nn 的严格递增数组 aa,以及一个与所有数组元素均不相等的数 xx。你要确定 xx 应插入数组的哪个位置,保持数组递增。一共有 n+1n+1 种可能的插入位置。

每次可以询问 xx 与 aia_i 的大小关系,代价为 costi\mathrm{cost}_i。可以根据已有的询问结果决定下一次询问哪个位置,直到能确定插入位置。一个策略的代价是它在最坏情况下的询问代价之和。

给定 cost\mathrm{cost},求所有策略中最小的最坏代价。

输入格式

输入一行,由 nn 个数字组成。第 ii 个数字是 costi\mathrm{cost}_i,数字之间没有空格。

输出格式

一行一个整数,表示答案。

样例

111
2

数据范围

1≤n≤1051\le n\le10^5,1≤costi≤91\le\mathrm{cost}_i\le9。

  • 对于 10%10\% 的数据,所有 costi=1\mathrm{cost}_i=1。
  • 另有 10%10\% 的数据,n≤100n\le100。
  • 另有 30%30\% 的数据,n≤2000n\le2000。

原 PDF 题面