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); } }
Leave A Comment