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.

public void solve(int testNumber, InputReader in, OutputWriter out) {
        int n = in.readInt();
        int cost = Integer.MAX_VALUE;
        int[] count = new int[250]; //how many energy we got
        int[] a = new int[n];
        for (int i = 0; i < a.length; i++) {
            a[i] = in.readInt();
        }
        int[] b = new int[n];
        for (int i = 0; i < b.length; i++) {
            b[i] = in.readInt();
        }
        IntPair[] pairs = new IntPair[n];
        for (int i = 0; i < n; i++) {
            pairs[i] = new IntPair(a[i],b[i]);
        }
        Arrays.sort(pairs);// sort by length of leg
        int[] pre = new int[n+1]; // pre[i] = if i is the max length leg, AT LEAST how many energy we need to cut down all legs with length large than pre[i]
        int p = n;
        for (int i = n-1; i >= 0; i--) {
            pre[p-1] = pairs[i].second + pre[p];
            p--;
        }
        int i = 0;
        while (i < n){
            int j = i;
            while (j < pairs.length)
                if (pairs[j].first == pairs[i].first )
                    j++;
            int need = (j - i) * 2 - 1;
            int cur = j - need;
            int find = Math.max(cur,0); // how many leg we need to find, cur could be negative, if we already reach the condition
            int sum = pre[j];
            for (int k = 1; find>0; k++) { // search from small energy cost legs
                int l = Math.min(find,count[k]);
                sum+=l*k; // add the energy cost
                find-=l;
            }
            while (i<j) {
                count[pairs[i].second]++;       
                i++;
            }
            cost = Math.min(cost,sum);
        }
        out.print(cost);
    }