题解 AT_abc294F【Sugar Water 2】

_Imaginary_ · 2023-03-19 21:25:27 · 题解

Problem

有两组糖水，分别有 n 杯（有 x1_i 吨糖和 y1_i 吨水）和 m 杯（有 x2_i 吨糖和 y2_i 吨水），求将它们两两混合后浓度第 k 大的混合浓度是多少。

Solution

我们先对 \frac{100x}{x+y} 进行变形。

要求浓度第 k 大，也就是求 \frac{y1+y2}{x1+x2} 第 k 小。

观察到数据范围是 5\times 10^4，不难想到应该是一个多 \log 的做法。

于是，我们可以在外面套一个二分，转化求 \frac{y1+y2}{x1+x2}\ge t 的混合糖水种类数。

再进行变形，首先进行通分，得到

这时，我们可以先用 O(m+n) 的代价把所有的 y1-tx1 和 tx2-y2 求出来，这样问题进行了转化：

有两个数组 a,b，求有多少对 i,j 满足 a_i\ge b_j。

首先用 O(m\log m) 对 b 数组排序，然后枚举每个 a_i，用 O(n\log m) 的时间二分查找有多少个 b_i 比它小。

这样，由于 n 和 m 同阶，整个问题就用 O(n\log^2 n) 解决了。

Code

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define y1 y11
const int N=500005;
int n,m;
ll k;
ll x1[N],y1[N],x2[N],y2[N];
ld a[N];
int get(ld x)
{
    int L=1,R=m,mid;
    while(L<=R)
    {
        mid=(L+R)>>1;
        if(x>a[mid]) L=mid+1;
        else R=mid-1;
    }
    return R;
}
ll check(ld k)
{
    for(int i=1;i<=m;i++) a[i]=(ld)x2[i]*k-(ld)y2[i];
    sort(a+1,a+m+1);
    ll ans=0;
    for(int i=1;i<=n;i++)
        ans+=get((ld)y1[i]-k*(ld)x1[i]);
    return ans;
}
int main()
{
    scanf("%d%d%lld",&n,&m,&k);
    for(int i=1;i<=n;i++) scanf("%lld%lld",&x1[i],&y1[i]);
    for(int i=1;i<=m;i++) scanf("%lld%lld",&x2[i],&y2[i]);
    ld L=0.0,R=1e20,mid;
    while(R-L>1e-14)
    {
        mid=(L+R)/2.0;
        if(check(mid)>=1ll*n*m-k+1) L=mid;
        else R=mid; 
    }
    printf("%.11Lf",100.0/(1.0+L));
    return 0;
}

后记

个人观点：