01分数规划POJ2976（简单模板题）

Dropping tests

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 7276		Accepted: 2523

Description

In a certain course, you take n tests. If you get a_i out of b_i questions correct on test i, your cumulative average is defined to be

Given your test scores and a positive integer k, determine how high you can make your cumulative average if you are allowed to drop any k of your test scores.

Suppose you take 3 tests with scores of 5/5, 0/1, and 2/6. Without dropping any tests, your cumulative average is . However, if you drop the third test, your cumulative average becomes .

Input

The input test file will contain multiple test cases, each containing exactly three lines. The first line contains two integers, 1 ≤ n ≤ 1000 and 0 ≤ k < n. The second line contains n integers indicating a_i for all i. The third line contains n positive integers indicating b_ifor all i. It is guaranteed that 0 ≤ a_i ≤ b_i ≤ 1, 000, 000, 000. The end-of-file is marked by a test case with n = k = 0 and should not be processed.

Output

For each test case, write a single line with the highest cumulative average possible after dropping k of the given test scores. The average should be rounded to the nearest integer.

Sample Input

Sample Output

83
100

Hint

To avoid ambiguities due to rounding errors, the judge tests have been constructed so that all answers are at least 0.001 away from a decision boundary (i.e., you can assume that the average is never 83.4997).

题意：给定n个二元组(a,b)，删除k个二元组，使得剩下的a元素之和与b元素之和的比率最大，最后的比率乘于100，然后输出跟最大比率最接近的整数

分析：设r=sigma(ai*xi)/sigma(bi*xi);其中xi={0,1},sigma(xi)=n-k,设R为最优值，

即：r<=R

即：sigma(ai*xi)/sigma(bi*xi)<=R

即：sigma(ai*xi)-sigma(R*bi*xi)<=0

也就是说sigma(ai*xi)-sigma(R*bi*xi)的最大值为0，

等价于 sigma((ai-R*bi)*xi)的最大值等于0；

因为h(r)=sigma((ai-R*bi)*xi)为单调递减函数，

所以可以二分求

#include"stdio.h"
#include"algorithm"
#include"string.h"
#include"iostream"
#include"queue"
#include"map"
#include"stack"
#include"cmath"
#include"vector"
#include"string"
#define M 1009
#define N 20003
#define eps 1e-7
#define mod 123456
#define inf 100000000
using namespace std;
int a[M],b[M],n,k;
double s[M];
int cmp(double a,double b)
{
    return a>b;
}
double fun(int n,double r)
{
    for(int i=1;i<=n;i++)
        s[i]=a[i]-r*b[i];
    sort(s+1,s+n+1,cmp);
    double sum=0;
    for(int i=1;i<=n-k;i++)
        sum+=s[i];
    return sum;
}
int main()
{
    while(scanf("%d%d",&n,&k),n||k)
    {
        double l=0,r=0,mid=0;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            r+=a[i];
        }
        for(int i=1;i<=n;i++)
            scanf("%d",&b[i]);
        while(r-l>eps)
        {
            mid=(l+r)/2;
            double msg=fun(n,mid);
            if(msg<0)
            {
                r=mid;
            }
            else
            {
                l=mid;
            }
        }
        printf("%.0lf
",r*100);
    }
    return 0;
}