P1570 题解#

题目分析#

刚开始做这道题可能没什么思路，所以我们先从式子入手：

假设存在最优解ans： $ans=\frac{\sum v_i}{\sum c_i}$

转化得 $ans\times\sum c_i=\sum v_i$

移项得 $ans\times \sum c_i-\sum v_i=0$

可见，当式子的结果趋向 $0$ 时，ans是最优解。

所以我们可以设 $f(ans)=ans\times\sum c_i-\sum v_i$

显然， $f(ans)$ 是一个一次函数，具有单调性。这个时候就会想到可以使用二分答案来解决这个问题。

既然使用二分答案来解决，首先应该考虑边界问题，这道题的边界比较好设定，左端点显然为 $0$ ，而右端点的设定，我们秉持着不怕大只怕小的原则，可以将其设定为 $\sum v_i$ 。

然后考虑check函数问题，思考之后可以发现，我们只需要判断在ans确定的情况下，最优的取法。所以考虑贪心，把每种调料的 $f(ans)$ 计算出来，从小到大排序之后取前 $m$ 个调料的一次函数值并累加。计算之后的数值与零相比较，如果小于零的话，说明 $ans$ 还可以更大，反之则应该更小。

到这里，这道题目就ac了，要注意好细节问题。

1
#include<bits/stdc++.h>
2
using namespace std;
3
#define int long long
4
int n,m,cnt=0;;
5
struct coffee{
6
    int v,c;
7
    double tot;
8
}a[10010];
9
void read(){
10
    cin>>n>>m;
11
    for(int i=1;i<=n;i++){
12
        cin>>a[i].v;cnt+=a[i].v;
13
    }
14
    for(int i=1;i<=n;i++){
15
        cin>>a[i].c;
16
    }
17
}
18
bool cmp(coffee a,coffee b){
19
    return a.tot<b.tot;
20
}
21
bool check(double x){
22
    for(int i=1;i<=n;i++){
23
        a[i].tot=x*a[i].c-a[i].v;
24
    }
25
    double sum=0;
26
    sort(a+1,a+n+1,cmp);
27
    for(int i=1;i<=m;i++){
28
        sum+=a[i].tot;
29
    }
30
    return sum<=0;
31
}
32
double search(){
33
    double l=0,r=cnt;
34
    while(r-l>=1e-5){
35
        double mid=(l+r)/2.0;
36
        //cout<<mid<<endl;
37
        if(check(mid)){
38
            l=mid;
39
        }
40
        else{
41
            r=mid;
42
        }
43
    }
44
    return l;
45
}
46
signed main(){
47
    read();
48
    double ans=search();
49
    printf(“%.3lf”,ans);
50
    return 0;
51
}