cf Educational Codeforces Round 40 E. Water Taps

原题：

E. Water Taps
time limit per test2 seconds
memory limit per test256 megabytes

inputstandard input
outputstandard output

Consider a system of n water taps all pouring water into the same container. The i-th water tap can be set to deliver any amount of water from 0 to ai ml per second (this amount may be a real number). The water delivered by i-th tap has temperature ti.

If for every i∈[1,n]$i\in [1,n]$ you set i-th tap to deliver exactly xi ml of water per second, then the resulting temperature of water will be ∑ni=0xiti∑ni=0xi$\frac{\sum _{i=0}^n{x}_i{t}_i}{\sum _{i=0}^n{x}_i}$(if ∑ni=0xi=0$\sum _{i=0}^n{x}_i=0$ , then to avoid division by zero we state that the resulting water temperature is 0).

You have to set all the water taps in such a way that the resulting temperature is exactly T. What is the maximum amount of water you may get per second if its temperature has to be T?

Input
The first line contains two integers n and T (1 ≤ n ≤ 200000, 1 ≤ T ≤ 10^6) — the number of water taps and the desired temperature of water, respectively.

The second line contains n integers a1, a2, …, an (1 ≤ ai ≤ 10^6) where ai is the maximum amount of water i-th tap can deliver per second.

The third line contains n integers t1, t2, …, tn (1 ≤ ti ≤ 10^6) — the temperature of water each tap delivers.

Output
Print the maximum possible amount of water with temperature exactly T you can get per second (if it is impossible to obtain water with such temperature, then the answer is considered to be 0).

Your answer is considered correct if its absolute or relative error doesn’t exceed 10^ - 6.

Examples

input
2 100
3 10
50 150
output
6.000000000000000

input
3 9
5 5 30
6 6 10
output
40.000000000000000

input
2 12
1 3
10 15
output
1.666666666666667

中文：

给你n个水龙头，每个水龙的每秒流量的限制可以是[0,ai]$[0,a_i]$，每个水龙头的水有温度ti$t_i$，现在给你一个温度T，让你用这个n个水龙头混合出温度为T的水，现在让你求能够混合出温度T所用的总流量最大是多少？

#include<bits/stdc++.h>
using namespace std;


const int maxn=200001;
const double eps=1e-6;

struct node
{
    double t,a;
};

int cmp(const node &x1,const node &x2)
{
    return x1.t<x2.t;
}

node ts[maxn];
int n,T;
double ans,l,r,mid;

bool C(double x)
{
    if (abs(x-eps)<=0)
        return false;

    double res1=x,res2=x;
    double low=0,high=0;

    double tmp=x*T;

    for(int i=1;i<=n;i++)
    {
        if (res1>ts[i].a)
        {
            low+=ts[i].a*ts[i].t;
            res1-=ts[i].a;
        }
        else
        {
            low+=res1*ts[i].t;//
            break;
        }
    }
    if(tmp<low)
        return false;

    for(int i=n;i>=1;i--)
    {
        if(res2>ts[i].a)
        {
            high+=ts[i].a*ts[i].t;
            res2-=ts[i].a;
        }
        else
        {
            high+=res2*ts[i].t;
            break;
        }
    }
    if(tmp>high)
        return false;

    return true;
}


int main()
{
    ios::sync_with_stdio(false);
    while(cin>>n>>T)
    {
        memset(ts,0,sizeof(ts));
        l=r=0;
        for(int i=1;i<=n;i++)
        {
            cin>>ts[i].a;
            r+=ts[i].a;
        }
        for(int i=1;i<=n;i++)
        {
            cin>>ts[i].t;
        }
        sort(ts+1,ts+n+1,cmp);
        for(int i=1;i<=100;i++)
        {
            mid=(l+r)/2;
            if (C(mid))
            {
                ans=mid;
                l=mid;
            }
            else
                r=mid;
        }
        cout<<fixed<<setprecision(12)<<ans<<endl;
    }

    return 0;
}

思路：

此题和挑战程序设计竞赛上面介绍二分法当中的求解最大化平均值的原理很像，如下(p144)。

利用二分的方法，设置C(X)为：可以选择最大流量为X满足混合后的温度为T。

∑ni=0xiti∑ni=0xi=T$$\frac{\sum _{i=0}^n{x}_i{t}_i}{\sum _{i=0}^n{x}_i}=T$$

实际上就是

∑i=0nxi=X$$\sum _{i=0}^n{x}_i=X$$

将第一个公式变形

∑i=0n(xiti−Txi)=0$$\sum _{i=0}^n(x_i{t}_i-T{x}_i)=0$$

∑i=0nxiti−XT=0$$\sum _{i=0}^n{x}_i{t}_i-XT=0$$

emmm，和书上的很像了~ 但是书上的那种方法是用贪心法依次按照最大值选取的，此题目也用到贪心的思想，但是，问题不同。

首先，如果给定水龙头的温度全都大于T或者全都小于T，那是肯定混合不出来温度T的水的。

所以，一定会有温度小于T的水龙头和温度大于T的水龙头。

那么，在选取水龙头的时候，温度低的和温度高的要分开来选，可以先对所有水龙头按照温度排序，依次记录高温high和低温low的累加xiti$x_i{t}_i$的值，同时二分得到的水量X要减去对应的xi$x_i$，直到发现X剩余的剩余的水量小于xi$x_i$为止，此时X剩余的水量就相当于将第xi$x_i$个水龙头的水量调成X的剩余值。

判断高温的high是否大于XT，低温的low是否小于XT即可。