【01分数规划】小咪买东西

古城微笑少年丶 2024-03-16 09:29 5阅读 0赞

**浅挂一下去年在知乎写的题解....**

**去年的东西貌似今年也不会呢**

[S-小咪买东西\_2021秋季算法入门班第三章习题：二分、三分、01 (nowcoder.com)][S-_2021_01 _nowcoder.com]

题意：  
![029fc28c4907465c8db9ef69318743c8.png][]

思路：

01分数规划问题的通解是二分

![55d59465da5a4a92a5afa47e527b86a2.png][]  
![9f6097cb921f47849ecb138bccff3803.png][]

Code：

（大一写的代码QwQ)

/*
     [[ ⣇⣿⠘⣿⣿⣿⡿⡿⣟⣟⢟⢟⢝⠵⡝⣿⡿⢂⣼⣿⣷⣌⠩⡫⡻⣝⠹⢿⣿⣷ ]],
     [[ ⡆⣿⣆⠱⣝⡵⣝⢅⠙⣿⢕⢕⢕⢕⢝⣥⢒⠅⣿⣿⣿⡿⣳⣌⠪⡪⣡⢑⢝⣇ ]],
     [[ ⡆⣿⣿⣦⠹⣳⣳⣕⢅⠈⢗⢕⢕⢕⢕⢕⢈⢆⠟⠋⠉⠁⠉⠉⠁⠈⠼⢐⢕⢽ ]],
     [[ ⡗⢰⣶⣶⣦⣝⢝⢕⢕⠅⡆⢕⢕⢕⢕⢕⣴⠏⣠⡶⠛⡉⡉⡛⢶⣦⡀⠐⣕⢕ ]],
     [[ ⡝⡄⢻⢟⣿⣿⣷⣕⣕⣅⣿⣔⣕⣵⣵⣿⣿⢠⣿⢠⣮⡈⣌⠨⠅⠹⣷⡀⢱⢕ ]],
     [[ ⡝⡵⠟⠈⢀⣀⣀⡀⠉⢿⣿⣿⣿⣿⣿⣿⣿⣼⣿⢈⡋⠴⢿⡟⣡⡇⣿⡇⡀⢕ ]],
     [[ ⡝⠁⣠⣾⠟⡉⡉⡉⠻⣦⣻⣿⣿⣿⣿⣿⣿⣿⣿⣧⠸⣿⣦⣥⣿⡇⡿⣰⢗⢄ ]],
     [[ ⠁⢰⣿⡏⣴⣌⠈⣌⠡⠈⢻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣬⣉⣉⣁⣄⢖⢕⢕⢕ ]],
     [[ ⡀⢻⣿⡇⢙⠁⠴⢿⡟⣡⡆⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣵⣵⣿ ]],
     [[ ⡻⣄⣻⣿⣌⠘⢿⣷⣥⣿⠇⣿⣿⣿⣿⣿⣿⠛⠻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿ ]],
     [[ ⣷⢄⠻⣿⣟⠿⠦⠍⠉⣡⣾⣿⣿⣿⣿⣿⣿⢸⣿⣦⠙⣿⣿⣿⣿⣿⣿⣿⣿⠟ ]],
     [[ ⡕⡑⣑⣈⣻⢗⢟⢞⢝⣻⣿⣿⣿⣿⣿⣿⣿⠸⣿⠿⠃⣿⣿⣿⣿⣿⣿⡿⠁⣠ ]],
     [[ ⡝⡵⡈⢟⢕⢕⢕⢕⣵⣿⣿⣿⣿⣿⣿⣿⣿⣿⣶⣶⣿⣿⣿⣿⣿⠿⠋⣀⣈⠙ ]],
     [[ ⡝⡵⡕⡀⠑⠳⠿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠿⠛⢉⡠⡲⡫⡪⡪⡣ ]],
     */
    #include <bits/stdc++.h>
    #include <stdio.h>
    #include <iostream>
    #include <math.h>
    #include <string.h>
    #include <ctype.h>
    #include <map>
    #include <string>
    #include <vector>
    #include <list>
    #include <algorithm>
    #include <float.h>
    #define max(a,b) (a>b?a:b)
    #define min(a,b) (a<b?a:b)
    #define gcd(a,b) __gcd(a,b)
    #define lcm(a,b) a/gcd(a,b)*b
    #define low(x) (x&-x)
    #define ll long long
    #define mnf 0x3f3f3f3f
    #define inf 0xc0c0c0c0
    #define rep(i,x,y) for(int i=x; i<=y; i++) 
    #define pre(i,x,y) for(int i=x; i>=y; i--)
    using namespace std;
    inline int rd(){
        char ch=getchar(); int nega=1; while(!isdigit(ch)) {if(ch=='-') nega=-1; ch=getchar();}
        int ans=0; while(isdigit(ch)) {ans=ans*10+ch-48;ch=getchar();}
        if(nega==-1) return -ans;
        return ans;
    }
    const int mxn=2e5+10;
    int n,k;
    int v[mxn],c[mxn];
    bool check(double x){
        double w[mxn],res=0;
        rep(i,1,n){
            w[i]=v[i]-x*c[i];
        }
        sort(w+1,w+1+n,greater<double>());
        for(int i=1;i<=k;i++){
            res+=w[i];
        }
        if(res>0) return true;
        else return false;
    }
    void solve(){
        int ans;
        n=rd(),k=rd();
        rep(i,1,n){
            c[i]=rd();
            v[i]=rd();
        }
        int l=0,r=1e9;
        while(l<=r){
            int mid=l+r>>1;
            if(check(mid)){
                ans=mid;
                l=mid+1;
            }else r=mid-1;
        }
        printf("%d\n",ans);
    }
    int main(){
        ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
        int T=rd();
        while(T--){
            solve();
        }
        return 0;
    }

[S-_2021_01 _nowcoder.com]: https://ac.nowcoder.com/acm/contest/22353/S
[029fc28c4907465c8db9ef69318743c8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/6399439030f540f1866a584634ab6cf5.png
[55d59465da5a4a92a5afa47e527b86a2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/2aceea612fd542538be3f3b693262abb.png
[9f6097cb921f47849ecb138bccff3803.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/0aa7d8b41cb047de8a3c9d59e4580ba5.png