P1570 KC喝咖啡

题目分析：

  • 一个裸的01分数问题
  • 答案区间[l,r] (l = 0,r = inf)




代码如下：

#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#include<set>

using namespace std;

#define inf 0x3f3f3f3f
#define eps 1e-6
#define db double
#define ll long long
#define  mm(a,x) memset(a,x,sizeof a)
#define pii pair<int,int>
#define pb push_back
#define el endl
#define debug(x) cerr<<#x<<" = "<<x<<endl
#define fgx cerr<<"-------------------------"<<endl
#define shutio ios::sync_with_stdio(false),cin.tie(0)
#define  mk make_pair
#define lowbit(x) (x) & (-x)
#define fi first
#define se second

const int N = 210;

int n,m;
struct Node{
    db v,c,w;
}node[N];

bool cmp(Node a,Node b){
    return a.w > b.w;    
}

bool check(db x){
    db s = 0;
    for(int i = 0; i < n; i ++ ){
        node[i].w = node[i].v - x * node[i].c;
    }
    sort(node,node + n,cmp);    
    for(int i = 0; i < m; i ++ ){
        s += node[i].w;
    }
    return s >= 0;
}

int main() {
    shutio;
    cin >> n >> m;
    for(int i = 0; i < n; i ++ ){
        cin >> node[i].v;
    }
    for(int i = 0; i < n; i ++ ){
        cin >> node[i].c;
    }    
    db l = 0,r = inf;
    while(r - l > eps){
        db mid = (l + r) / 2;
        if(check(mid)) l = mid;
        else r = mid;
    }
    printf("%.3f",l);
    return 0;
}