题解 P1570 【KC喝咖啡】

· · 题解

好久没有写二分答案了，来复习复习。顺便补充个像样的有\LaTeX的题解。

刚开始看到题目还以为是01背包，但却是求平均值最大，故不考虑。

但是不好思考呢……那先从式子入手：

假设存在一种最优解ans，则

\large ans=\frac{\sum^m_{i=1}v_i}{\sum^m_{i=1}c_i}

式子太复杂？尝试化一下。

\text{去分母得，}\sum^m_{i=1}c_i·ans=\sum^m_{i=1}v_i \text{移项得，}\sum^m_{i=1}c_i·ans-\sum^m_{i=1}v_i=0

观察式子，不难发现最优解ans会使得左边=0，因此我们的目标就是尽可能地的靠近0。加上ans具有单调性，这时就考虑到二分。

check()也就很好写了。由于我们想让左边尽可能<0，则考虑贪心，排序并选前m个最小的权值并得到之和tot。

此时要对check()得到的tot进行分类讨论了：

另外，由于有小数，二分结束条件l,r之间就不是r-l\ge 1，而是形如r-l\le 10^{-5}保证精度。

时间复杂度：

综上所述，时间复杂度为：

\large\Theta(n+(m+n\log n)\log\max\{\frac{v_i}{v_i}\}) \large\approx\Theta(n\log n \log \max\{\frac{v_i}{v_i}\})

最坏也不过达到大约2\times 10^4。

讲得很细了，代码注释就不给那么多了。分析里都有。

代码如下：

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

const int MAXN=500;
int n,m;
struct coffee
{
    int v,t;
    double avr;//算权值t*x-v
    bool operator<(const coffee a)const
    {
        return avr<a.avr;
    }
}a[MAXN];
double ans,l,r;

void input(void)
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
     cin>>a[i].v;
    for(int i=1;i<=n;i++)
     cin>>a[i].t;
}

bool check(const double x)
{
    for(int i=1;i<=n;i++)
     a[i].avr=x*a[i].t-a[i].v;//算每个的权值
    sort(a+1,a+n+1);//从小到大排序
    double tot=0;
    for(int i=1;i<=m;i++)//取前m个小的
     tot+=a[i].avr;
    return tot<=0;
}

void binary(void)
{
    for(int i=1;i<=n;i++)
     if(a[i].v*1.0/a[i].t>r)
      r=a[i].v*1.0/a[i].t;//算出上界
    while(r-l>1e-5)
    {
        const double mid=(l+r)/2.0;
        if(check(mid))//注意分类讨论（这里结合二分求上下界）
         l=mid;
        else
         r=mid;
    }
    ans=l;
}

int main()
{
    input();
    binary();
    printf("%.3f\n",ans);
    return 0;
}

还没结束呢！

现在仔细想想，或许可以不用二分（优势在于避免分类讨论和上下界问题），考虑枚举x(x\in[0,\max\large\{\frac{v_i}{c_i}\}])，并进行check()，好像也不会超时。理论时间复杂度：

\Theta(n\log n \max\{\frac{v_i}{c_i}\})

最坏情况大约为1.5\times 10^8。

但实际题目中除非专门卡否则一般达不到这样的复杂度，加上编译器的优化和lg评测机的良好性能，卡一卡（甚至不用）就能过去。

当然以上只是个人看法，作者还没实践过。

完结撒花！✿✿ヽ(°▽°)ノ✿