有n对数，记做\(\{a_i,b_i\}\),现在你只能不选择k对数，使选出来的数a之和除以b之和乘以100最大，\(1 \leq k ≤ n ≤ 1000\)。

解

显然看到某某和除以某某和，就想到了分数规划，于是设

\[ans=\frac{\sum_{i=1}^nx_ia_i}{\sum_{i=1}^nx_ib_i}\]

所以二分式为

\[\sum_{i=1}^nx_i(a_i-ans\times b_i)\]

实际上问题即变成选出n-k对\((a_i-ans\times b_i)\)使之最大，于是我们最自然是考虑排序优化，而这个时间复杂度是我们所能接受的,接着按

照二分或者迭代去做即可。

参考代码：

二分

#include 
    
     #include 
     
      #include 
      
       #define il inline#define ri register#define db double#define exact 0.00000001int n,k;db a[2001],b[2001],c[2001];using namespace std;il bool check(db);il db dfs(db,db);int main(){    int i,j;    while(scanf("%d%d",&n,&k),n||k){        for(i=1;i<=n;++i)scanf("%lf",&a[i]);        for(i=1;i<=n;++i)scanf("%lf",&b[i]);        printf("%0.f\n",dfs(0,1));    }    return 0;}il bool check(db s){    int i;db j(0);    for(i=1;i<=n;++i)c[i]=a[i]-s*b[i];    sort(c+1,c+n+1);for(i=k+1;i<=n;++i)j+=c[i];    if(j>exact)return true;return false;}il db dfs(db l,db r){    db mid;    while(r-l>exact){        mid=(l+r)/2;        if(check(mid))l=mid+exact;        else r=mid-exact;    }return (l+r)*50;}
      
     
    

迭代

#include 
    
     #include 
     
      #include 
      
       #define il inline#define ri register#define db double#define exact 0.00000001using namespace std;struct save{    db data;int id;    il bool operator<(const save&x){        return data
       
        exact)l=son/mom;            else break;        }printf("%.0f\n",l*100);    }    return 0;}