（小声bb：话说好像下周就可以停课了(flag)！终于可以去见学长们啦~ 虽然月考挂了）

在这里学习的分数规划——>

简单总结一下

设函数f(r)=sigma(a[i]*x[i])-r*sigma(b[i]*x[i])

变形 f(r)=sigma((a[i]-r*b[i])*x[i])

假如r已知 若预处理出d[i]=a[i]-r*b[i] 那式子就变得很简洁了 f(r)=sigma(d[i]*x[i]) 

我们分析一下f(r) 假设f(r)>0 会发生什么呢？ 代回原式

即sigma(a[i]*x[i])/sigma(b[i]*x[i])>r

这说明还有另一个解比当前的r好！

所以满足二分的性质 那么若f(r)<0 此f(r)<0是没有意义的，因为这时候的r是不能够被取得的

然后就没了 对于二分的check 这道题只需要把所有d排序 找前k个最优的 QWQ

#include
     
      #include
      
       #include
       
        #include
        
         #define N 1005#define eps    1e-7using namespace std;int n,k;double a[N],b[N],d[N];inline double check(double num){    for(int i=1;i<=n;i++)    d[i]=a[i]-num*b[i];    sort(d+1,d+n+1);    double ans=0;    for(int i=k+1;i<=n;i++)    ans+=d[i];    return ans;}int main(){    while(scanf("%d%d",&n,&k),n||k)    {        memset(a,0,sizeof(a));        memset(b,0,sizeof(b));        memset(d,0,sizeof(d));        for(int i=1;i<=n;i++)    cin>>a[i];        for(int i=1;i<=n;i++)    cin>>b[i];        double l=0,r=1000,m;        while(l+eps
         
          0)    l=m;             else r=m;        }        printf("%.0lf\n",m*100);    }    return 0;}