来源：

Northeastern Europe 2005, Northern Subregion

思路：

分数规划经典题。二分分数值$x$，判断其是否满足$\sum (v - w \times m) \geq 0$即可。

针对$v - w \times m$从大到小排序，然后对前$k$项求和，检验是否非负。

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 inline int getint() { 7     char ch; 8     while(!isdigit(ch=getchar())); 9     int x=ch^'0';10     while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');11     return x;12 }13 const double eps=1e-6;14 const int N=100000;15 int n,k;16 struct Jewel {17     int v,w,id;18     double sum;19     bool operator > (const Jewel &x) const {20         return sum>x.sum;21     }22 };23 Jewel j[N];24 std::vector
          
            ans;25 inline bool check(const double x) {26 ans.clear();27 for(int i=0;i
           
            ());31 double sum=0;32 for(int i=0;i
            
             =0;37 }38 int main() {39 n=getint(),k=getint();40 for(int i=0;i
             
              =eps) {47 double mid=(l+r)/2;48 if(check(mid)) {49 l=mid;50 }51 else {52 r=mid;53 }54 }55 for(unsigned i=0;i