AtCoder 1807 食塩水

题意

有 \(n\) 瓶食盐水，第 \(i\) 瓶为质量 \(w_i\)，浓度 \(p_i\%\) 的食盐水，需要选出 \(k\) 瓶食盐水混合在一起，问最大浓度。

\(\texttt{Data Range:}1\leq n,k\leq 1000\)

题解

二分答案。

一开始在想各种贪心，然后各种贪心都假了，但是注意到这个东西是有单调性，（如果存在一种方案混合出来的食盐水浓度大于 \(p\) 那么也一定存在一种方案的浓度大于比 \(p\) 小的值），所以可以二分答案变成判定性问题。

现在考虑能不能选出 \(k\) 瓶食盐水混合起来浓度大于某个二分到的 \(p\)，也即：

\[\frac{\sum\limits_{i=1}^{k}w_ip_i}{\sum\limits_{i=1}^{k}w_i}\geq p
\]

乘过去再移过来

\[\sum\limits_{i=1}^{k}w_i(p_i-p)\geq 0
\]

所以说我们只需要对 \(w_i(p_i-p)\) 排序然后贪心选最大的 \(k\) 个即可，实现可能有一些细节需要注意。

代码

#include<bits/stdc++.h>

using namespace std;

typedef int ll;

typedef long long int li;

typedef long double db;

const ll MAXN=2e5+51;

const db eps=1e-10;

struct Node{

    ll p,w;

};

Node x[MAXN];

ll n,kk;

db l,r,mid;

db c[MAXN];

inline ll read()

{

    register ll num=0,neg=1;

    register char ch=getchar();

    while(!isdigit(ch)&&ch!='-')

    {

        ch=getchar();

    }

    if(ch=='-')

    {

        neg=-1;

        ch=getchar();

    }

    while(isdigit(ch))

    {

        num=(num<<3)+(num<<1)+(ch-'0');

        ch=getchar();

    }

    return num*neg;

}

inline ll check(db mid)

{

    db c2=0;

    for(register int i=1;i<=n;i++)

    {

        c[i]=(x[i].p-mid)*x[i].w;

    }

    sort(c+1,c+n+1,greater<db>());

    for(register int i=1;i<=kk;i++)

    {

        c2+=c[i];

    }

    return c2>=0;

}

int main()

{

    n=read(),kk=read(),l=0,r=100;

    for(register int i=1;i<=n;i++)

    {

        x[i].w=read(),x[i].p=read();

    }

    while(r-l>=eps)

    {

        mid=(l+r)/2;

        check(mid)?l=mid:r=mid;

    }

    printf("%.9Lf\n",l);

}

巴特西

AtCoder 1807 食塩水

题意

题解

代码

最新文章

热门文章