本文主要是介绍Codeforces Round #311 (Div. 2) Problem B，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
2015年7月2日
题目描述：输入两个整数n(1 <= n <= 10^5)，w(1 <= w <= 10^9)。n表示有n个男孩和n个女孩，共2n个人；w表示有一个容器的盛有w毫升的水，然后第二行输入2n整数arr[i](1 <= arr[i] <= 10^9)，表示有2n个容器,第i个容器的容量是arr[i],让后用着w毫升水在这2 * n个容器里倒水，有两个条件：倒出的水总容量小于等于w，每个男孩的杯子的盛水是n任意女孩的两倍，求能倒出水最大容量是多少。
例如：
input
1 5
2 3
output
4.5
样例解释：有1个男孩，1个女孩，一个杯子的容量是2，一个杯子的容量是3，在容量大小为2的杯子倒入1.5毫升的水，这个杯子被女孩占用，另一个杯子的容量是3，倒入3毫升的水，总倒出的水是4.5毫升小于等于5毫升，并且女孩的水容量是男孩的一半。
题目很明确地说，每一个女生所盛的水是任意一个男生的一半，通过这个条件能够得到一个结论：每个女生所盛的水是相同的，男生也是相同的，并且女生的所盛水的容量是男生的一半。
给了2n个杯子盛水。将这2n个杯子按容量的大小排序将arr[0]作为女孩的基础杯子容量，arr[n]作为男孩的基础杯子，将问题的规模抽象出来就是：
在[0,min(arr[0], arr[n] / 2)]中寻找一个值x，这个x是一个女孩的最终的容量，所以一个男孩的容量就是2x，这个x是属于[0, arr[0]], 2x 属于[0, arr[n]],并且要让这个x尽量大，此时会想到的一个算法就是二分查找去搜索这个x。
应为数据x有可能会是浮点数，所以比较的时候就会出现浮点数跟整数比较，直接用“==”比较是不合理的，是有精度遗失的，这里的处理是用一个EPS来处理精度问题，a <= b可以等价转化为(b - a)>= EPS。这个EPS的精度要去多大是一个很不明确的值，有时取得过大是会出现精度损失，过小会比较耗时(即有可能会超时)，据测试这里取1e-11，1e-12是合理的。
#include <bits/stdc++.h>
#define MAXN 200007
#define EPS 1e-11 //精度问题一定要取合理，太小有误差，太大会超时
using namespace std;
double arr[MAXN];
int main()
{int n;double w;cin >> n >> w;for(int i = 0; i < 2 * n; ++i)scanf("%lf", &arr[i]);sort(arr, arr + 2 * n);double L = 0, R = min(arr[0], arr[n] / 2); //在[0, min(arr[0], arr[n] / 2)]中二分搜索答案while(fabs(R - L) > EPS) {//当R - L大于EPS时就继续找更优的值double M = L + (R - L) / 2;if((arr[n] - M * 2) >= EPS && (w - M * 3 * n) >= EPS) L = M;//如果M是满足条件的值，则试图向右边区间找更合理的答案else R = M;//否则在左边的区间找更合理的答案}printf("%lf\n", L * 3 * n);return 0;
}
转载请注明出处：http://blog.csdn.net/royecode
这篇关于Codeforces Round #311 (Div. 2) Problem B的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
