Codeforces Round

B. Pasha and Tea

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Pasha decided to invite his friends to a tea party. For that occasion, he has
a large teapot with the capacity of _w_ milliliters and 2 _n_ tea cups, each
cup is for one of Pasha’s friends. The _i_ -th cup can hold at most _a_ _i_
milliliters of water.

It turned out that among Pasha’s friends there are exactly _n_ boys and
exactly _n_ girls and all of them are going to come to the tea party. To
please everyone, Pasha decided to pour the water for the tea as follows:

Pasha can boil the teapot exactly once by pouring there at most _w_ milliliters of water;
Pasha pours the same amount of water to each girl;
Pasha pours the same amount of water to each boy;
if each girl gets _x_ milliliters of water, then each boy gets 2 _x_ milliliters of water.

In the other words, each boy should get two times more water than each girl
does.

Pasha is very kind and polite, so he wants to maximize the total amount of the
water that he pours to his friends. Your task is to help him and determine the
optimum distribution of cups between Pasha’s friends.

Input

The first line of the input contains two integers, _n_ and _w_ ( 1 ≤ _n_ ≤
10 5 , 1 ≤ _w_ ≤ 10 9 ) — the number of Pasha’s friends that are boys
(equal to the number of Pasha’s friends that are girls) and the capacity of
Pasha’s teapot in milliliters.

The second line of the input contains the sequence of integers _a_ _i_ ( 1 ≤
_a_ _i_ ≤ 10 9 , 1 ≤ _i_ ≤ 2 _n_ ) — the capacities of Pasha’s tea cups in
milliliters.

Output

Print a single real number — the maximum total amount of water in milliliters
that Pasha can pour to his friends without violating the given conditions.
Your answer will be considered correct if its absolute or relative error
doesn’t exceed 10 - 6 .

Sample test(s)

input

2 4
1 1 1 1

output

input

3 18
4 4 4 2 2 2

output

input

1 5
2 3

output

4.5

二分答案即可

#include <stdio.h>
#include <ctime>
#include <math.h>
#include <limits.h>
#include <complex>
#include <string>
#include <functional>
#include <iterator>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <list>
#include <bitset>
#include <sstream>
#include <iomanip>
#include <fstream>
#include <iostream>
#include <ctime>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <time.h>
#include <ctype.h>
#include <string.h>
#include <assert.h>

using namespace std;

int n, w;
double p[200010];

int main()

{
    while (cin >> n)
    {
        cin >> w;
        for (int i = 1; i <= n * 2; i++)
            scanf("%lf",&p[i]);
        sort(p + 1, p + 1 + 2 * n);
        int t1 = p[1];
        int t2 = p[n + 1];
        double ans;

        if (t2 >= t1 * 2)  //yes
        {
            double left = 0;
            double right = w;
            double mid;
            while (left + 0.000000001 <right)
            {
                mid = (left + right) / 2;
                //n*X + n*X/2 <= mid 
                double x = mid / n / 3;
                if (x <= t1)
                {
                    left = mid;
                    ans = mid;
                }
                else
                    right = mid;
            }
        }
        else
        {
            double left = 0;
            double right = w;
            double mid;
            while (left + 0.000000001 <right)
            {
                mid = (left + right) / 2;
                //n*X + n*X/2 <= mid 
                double x = mid * 2 / n / 3;
                if (x <= t2)
                {
                    left = mid;
                    ans = mid;
                }
                else
                    right = mid;
            }
        }
        printf("%.8lf\n",ans);
    }
    return 0;
}