poj2976：题目链接

题目大意：给出n个对 ，可以从中最多排除k个对，求∑a/∑b的最大值。

0-1分数规划：x = ∑a/∑b --> 0 = ∑a-x*∑b --> g(x) = max(∑a-x*∑b)，可以求出g(x)是一个关于x的单调递减的函数，当g(x)=0的时候，x为要求的最大值。因为这个单调性，所以可以使用二分求解

假设s为要求的值。

g(x) == 0 --> x = s ;

g(x) > 0 --> x < s ;

g(x) < 0 --> x > s ;

对于这个题目来说，g(x) = max( ∑( 100*ai - x*bi ) )，因为最多只能舍弃k个，所以将最小的k个中的负值舍弃，就可以得到最大值。

原本想学最大密度子图来着，看论文，从头学起，，，，百度文库连接

?

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       using namespace std ; #define eqs 1e-9 struct node{ double a , b ; }p[1100] ; int n , k ; double c[1100] ; double solve(double s) { double ans = 0 ; for(int i = 0 ; i < n ; i++) c[i] = 100.0*p[i].a - s*p[i].b ; sort(c,c+n) ; for(int i = 0 ; i < n ; i++) { if( i < k ){ if( c[i] >= eqs ) ans += c[i] ; } else ans += c[i] ; } return ans ; } int main() { int i , j ; double low , mid , high , temp ; while( scanf("%d %d", &n, &k) && n+k > 0 ) { for(i = 0 , high = 0 ; i < n ; i++) { scanf("%lf", &p[i].a) ; high += p[i].a ; } for(i = 0 ; i < n ; i++) scanf("%lf", &p[i].b) ; low = mid = 0 ; high *= 100.0 ; while( high-low >= eqs ) { mid = (high + low) / 2.0 ; temp = solve(mid) ; if( fabs(temp) < eqs ) break ; else if( temp < 0 ) high = mid ; else low = mid ; } printf("%d\n", (int)(mid+0.5)) ; } return 0 ; } 
     
    
   
  

?