Codeforces Round #311 (Div. 2) C. Arthur and Table

原题:http://codeforces.com/contest/557/problem/C


题目大意: 一个桌子, n条腿, 每个腿的长度不同, 定义一个平衡状态为: 最长腿的个数 >= 总数 / 2. 每个腿去除要花费的能量都不一样, 问最少多少能达到平衡.


分析: 这题开始做的时候, 有点糊涂, 以为是贪婪+暴力, 然后第八个test case 各种过不去.仔细一看有10万个腿.我x,那是桌子么.. 然后想dp, 又想反了, 最开始想的是,自顶向下的, 后来发现remove的次数太多, 每次remove都重复了, 才知道应该是从下往上容易做. 具体的思路是: Sort一下所有的腿长, 从最短的开始, 建立Pre数组, 记录如果选择当前的腿, 所需要砍除的所有比它高的腿的能量花费的合,即: Sum( cur_max<=i<=Pre.length){腿[i]}.然后另一个窍门是, 一共能量的范围只有200多, 建一个count数组, 记录所有的energy cost, 然后从小往大找能删除的腿. 找到就加到sum.