来源：
Northeastern Europe 2005, Northern Subregion
思路：
分数规划经典题。二分分数值$x$，判断其是否满足$sum (v - w imes m) geq 0$即可。
针对$v - w imes m$从大到小排序，然后对前$k$项求和，检验是否非负。
1 #include<cstdio> 2 #include<cctype> 3 #include<vector> 4 #include<algorithm> 5 #include<functional> 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<int> ans; 25 inline bool check(const double x) { 26 ans.clear(); 27 for(int i=0;i<n;i++) { 28 j[i].sum=j[i].v-j[i].w*x; 29 } 30 std::sort(&j[0],&j[n],std::greater<Jewel>()); 31 double sum=0; 32 for(int i=0;i<k;i++) { 33 sum+=j[i].sum; 34 ans.push_back(j[i].id); 35 } 36 return sum>=0; 37 } 38 int main() { 39 n=getint(),k=getint(); 40 for(int i=0;i<n;i++) { 41 j[i].v=getint(); 42 j[i].w=getint(); 43 j[i].id=i+1; 44 } 45 double l=0,r=1000000; 46 while(r-l>=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<ans.size();i++) { 56 printf("%d ",ans[i]); 57 } 58 return 0; 59 }