POJ 2976 Dropping tests —————— 01分数规划，二分

刺骨的言语ヽ痛彻心扉 2021-11-05 07:22 214阅读 0赞

# [POJ 2976 Dropping tests][] #

给出n个a和b，让选出n-k个使得  100 ∗ ∑ i = 1 n a i ∑ i = 1 n b i 100\*\\frac\{\\sum\_\{i=1\}^\{n\} a\_i\}\{\\sum\_\{i=1\}^\{n\}b\_i\} 100∗∑i=1nbi∑i=1nai 最大  
01规划问题，[看这里][Link 1]

看完就会了

这里用的是二分的方法

/*--------- Hongjie ----------*/
    /**
     *　　　　　　　　┏┓　　　┏┓+ +
     *　　　　　　　┏┛┻━━━┛┻┓ + +
     *　　　　　　　┃　　　　　　　┃
     *　　　　　　　┃　　　━　　　┃ ++ + + +
     *　　　　　　 ████━████ ┃+
     *　　　　　　　┃　　　　　　　┃ +
     *　　　　　　　┃　　　┻　　　┃
     *　　　　　　　┃　　　　　　　┃ + +
     *　　　　　　　┗━┓　　　┏━┛
     *　　　　　　　　　┃　　　┃
     *　　　　　　　　　┃　　　┃ + + + +
     *　　　　　　　　　┃　　　┃　　　　Code is far away from bug with the animal protecting
     *　　　　　　　　　┃　　　┃ + 　　　　神兽保佑,代码无bug
     *　　　　　　　　　┃　　　┃
     *　　　　　　　　　┃　　　┃　　+
     *　　　　　　　　　┃　 　　┗━━━┓ + +
     *　　　　　　　　　┃ 　　　　　　　┣┓
     *　　　　　　　　　┃ 　　　　　　　┏┛
     *　　　　　　　　　┗┓┓┏━┳┓┏┛ + + + +
     *　　　　　　　　　　┃┫┫　┃┫┫
     *　　　　　　　　　　┗┻┛　┗┻┛+ + + +
     */
    
    // #include<bits/stdc++.h>
    #include<map>
    #include<set>
    #include<queue>
    #include<stack>
    #include<deque>
    #include<cmath>
    #include<cstdio>
    #include<bitset>
    #include<string>
    #include<vector>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    
    typedef long long ll;
    typedef pair<int ,int> P;
    
    const int INF  = 0x3f3f3f3f;
    const int MAXN = 1e4+7;
    const double eps = 1e-5;
    ll a[MAXN],b[MAXN];
    double p[MAXN];
    int n, k;
    
    bool check(double x) {
        
            double ans = 0;
            for(int i=0;i<n;++i)
                    p[i] = 1.0*100*a[i] - 1.0*x*b[i];
            sort(p,p+n);
            for(int i=k;i<n;++i)
                    ans += p[i];
            return ans > eps;
    }
    
    int main(){
        
            // freopen("../in.txt","r",stdin);
            // freopen("../out.txt","w",stdout);
            ios::sync_with_stdio(0);
            cin.tie(0);
            while(cin>>n>>k) {
        
                    if(n==0 && k==0)        break;
                    for(int i=0;i<n;++i) {
        
                            cin>>a[i];
                    }
                    for(int i=0;i<n;++i) {
        
                            cin>>b[i];
                    }
                    double l = 0, r = 100.0,  mid;
                    while(r-l>eps) {
        
                            mid = (l+r)/2.0;
                            if(check(mid))  l = mid;
                            else r = mid;
                    }
                    printf("%.0lf\n",l);
            }
            return 0;
    }

[POJ 2976 Dropping tests]: http://poj.org/problem?id=2976
[Link 1]: https://www.cnblogs.com/perseawe/archive/2012/05/03/01fsgh.html