贪心

请朋友喝TEA问题

题目：

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 2n tea cups, each cup is for one of Pasha’s friends. The i-th cup can hold at most ai 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 2x 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 ≤ 105, 1 ≤ w ≤ 109) — 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 ai (1 ≤ ai ≤ 109, 1 ≤ i ≤ 2n) — 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
Examples
Input
2 4
1 1 1 1
Output
3
Input
3 18
4 4 4 2 2 2
Output
18
Input
1 5
2 3
Output
4.5
Note
Pasha also has candies that he is going to give to girls but that is another task…
题目大意：
Pasha邀请朋友喝茶，共有茶w，共有2n个人，男女各n人，有数组a[2n]，表示2*n个杯子的大小，其中男生喝的水为女生的二倍，男生喝的水量都相同，女生的水量都相同；问朋友们在规定的条件下可以喝多少水？
题解：

#include <iostream>
#include <cstring>
#include <algorithm>
#include <stdio.h>
using namespace std;
int main()
{
    int a[200200];
    int n,w;
    while(scanf("%d %d",&n,&w)!=EOF)
    {
        int i;
        for(i=0;i<2*n;i++)
            scanf("%d",&a[i]);
        sort(a,a+n*2);
        double sum;
        if(a[n]/2.0<=a[0]*1.0)
            sum=(a[n]/2.0+a[n])*n;
        else
            sum=(a[0]+a[0]*2)*n;
        if(sum>w)
            sum=w;
        printf("%lf\n",sum);
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

解析：
首先将杯子按照从小到大的顺序排列，然后找到男生的第一个，也就是下标为n的数，判断a[n]/2与a[0]之间的关系然后求出最大的sum；
注意：
c++中的sort()排序法比快速排序法快的多；