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了.