Codeforces Round #311 (Div. 2) B. Pasha and Tea

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

---

题目大意: 一个大小为w的茶壶, 给n个男孩儿,n个女孩儿倒茶. 一共有2n个杯子, 每个杯子的容量都不一样. 所有女孩儿喝x量的茶, 所有男孩儿需要喝2x量的茶. 问怎么倒能倒最多的茶.

---

分析: 一看以为是Greedy的题, 后来看了下tag, 发现是sorting, 能sort的就只有茶杯了, 于是把茶杯按容量从小到大排序. 一共有2n个茶杯. cup[0]是妹纸中拿到的最小的茶杯, 因为所有妹纸都喝一样多的茶,  所以最小茶杯的茶杯bound住妹纸们喝的总量, 同理, cup[n]是汉子中拿到的最小的茶杯, 它bound住所有汉子喝的茶. 所以妹纸们喝的总量是cup[0]*n, 汉子们喝的总量是cup[n]*n. 那么先给汉子倒茶还是先给妹纸倒茶? 这个不一定的, 要看cup[0]和cup[n]的大小, 如果cup[0]*2 > cups[n] 那么就要给汉子先倒茶, 反过来就要先给妹纸倒茶. 最后注意一下倒的总量不能超过w. 如果超过了 那么就是w了.

public void solve(int testNumber, InputReader in, OutputWriter out) {
        int n = in.readInt();
        long w = in.readLong();
        long[] cups = new long[2*n];
        for (int i = 0; i < cups.length; i++) {
            cups[i]  = in.readLong();
        }
        Arrays.sort(cups);
        if (cups[0] * 2 > cups[n]) {
            if (n * cups[n] + (double) n * cups[n] / 2 < w)
                out.print(n * cups[n] + (double) n * cups[n] / 2);
            else
                out.print(w);
        }
        else {
            if (n * cups[0] + n * cups[0] * 2 < w)
                out.print(n * cups[0] + n * cups[0] * 2);
            else
                out.print(w);
        }
    }