题解 P1570 【KC喝咖啡】

浅色调 · 2017-10-30 16:31:03 · 题解

二分答案+贪心

思路：一般最先想到的方法是把物品按照单位价值进行排序，从大到小地贪心进行选取。但是很明显这样去贪心很容易举出反例，于是我们考虑套用二分+贪心来解决。我们可以直接二分答案，区间l取0、r取单个物品的最大价值(注意精度开double)，然后对于我们二分出的值x，关键是如何check判断，稍稍运用下数学转换公式：sigma(vi)/sigma(ci)>=x，变形推导出sigma(vi-x*ci)>=0。因此，可以对vi-x*ci进行贪心排序选取前m个，最后只要判断这m个值的和是否大于等于0就ok了。

代码：

#include<bits/stdc++.h>
using namespace std;
int n,m;
struct query{
int v,c;double div;
}a[1000];
bool cmp(query a,query b){return a.div>b.div;}
inline bool check(double x)
{
    for(int i=1;i<=n;i++)a[i].div=a[i].v-x*a[i].c;
    sort(a+1,a+n+1,cmp);
    double tot=0;
    for(int i=1;i<=m;i++)tot+=a[i].div;
    return tot>=0;
}
int main()
{
    scanf("%d%d",&n,&m);
    double l=0,r,mid;
    for(int i=1;i<=n;i++)scanf("%d",&a[i].v);
    for(int i=1;i<=n;i++)scanf("%d",&a[i].c),r=r<a[i].v*1.0/a[i].c?a[i].v*1.0/a[i].c:r;
    while(r-l>1e-6)
    {
        mid=(l+r)/2;
        if(check(mid))l=mid;
        else r=mid;
    }
    printf("%.3lf",l);
    return 0;
}