程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> poj2976

poj2976

編輯:關於C++

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


 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved