poj2976

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 ;
}