Codeforces Round #318 [RussianCodeCup Thanks-Round] (Div. 2) A. Bear and Elections | 书脊

Codeforces Round #318 [RussianCodeCup Thanks-Round] (Div. 2) A. Bear and Elections | 书脊

Codeforces Round #318 [RussianCodeCup Thanks-Round] (Div. 2) A. Bear and Elections

原题: http://codeforces.com/contest/574/problem/A

---

题目大意: 给一个n的数的数组, 问如何让第一个数拿最少数组中别的数字的数,使得第一个数变成这个数组最大的数.

---

分析: 这题的做法很多, 我开始的时候暴了一下, 发现过不了, 暴的复杂度是O(n2), 看来能有lgn的做法. 后来想想, 假设第一个数是数组中最大的数, 那么就可以不用拿别的数, 如果第一个数不是数组中最大的数, 那么它最多拿的数, 应该是数组中最大的数. 假设数组: 5 1 11 2 8. 第一个数5不是数组中最大的数字, 那么我们可以假设, 最坏情况下, 我们最多拿11(11为数组中最大的数字), 使得5变成数组中最大的数字, 当然这个情况是最坏情况.

其次, 上面例子中的5 1 11 2 8的结果是4, 那么我们可以证明, 任何大于4的数字都是可以的. 因此, 我们可以通过二分搜索的办法, 搜索这个数字. 复杂度是o(nlgn), n是每次检查搜索结果的正确性, lg是二分.

Read full article from Codeforces Round #318 [RussianCodeCup Thanks-Round] (Div. 2) A. Bear and Elections | 书脊