1.题目描述:

Description

In a certain course, you take n tests. If you get ai out of bi 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 ai for all i. The third line contains n positive integers indicating bi for all i. It is guaranteed that 0 ≤ ai ≤ bi ≤ 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

3 1
5 0 2
5 1 6
4 2
1 2 7 9
5 6 7 9
0 0

Sample Output

83
100

2.题意概述:

给定n个二元组(a,b),扔掉k个二元组,使得剩下的a元素之和与b元素之和的比率最大。题目求的是 max(∑a[i] * x[i] / (b[i] * x[i]))   其中a,b都是一一对应的。 x[i]取0,1  并且 ∑x[i] = n – k。

0-1分数规划+二分

#include<bits/stdc++.h>
#define INF 0x7fffffff
#define esp 1e-15
using namespace std;
const int maxn=1e9+10;
long long n,k;
double a[maxn],b[maxn],y[maxn];
int judge(double x){
    for(int i=0;i<n;i++)
        y[i]=a[i]-x*b[i];
    sort(y,y+n,greater<double>());
    double sum=0;
    for(int i=0;i<n-k;i++)
        sum+=y[i];
    return sum>0;
}
int main(){
    while(~scanf("%lld%lld",&n,&k),n|k){
        for(int i=0;i<n;i++)
            scanf("%lf",&a[i]);
        for(int i=0;i<n;i++)
            scanf("lf",&b[i]);
        double l=0,r=INF;
        double mid;
        while(r-l>esp){
            mid=l+(r-l)/2;
            if(judge(mid))
                l=mid;
            else
                r=mid;
        }
        printf("%.0lf\n", mid * 100);
    }
    return 0;
}
#include<bits/stdc++.h>
#define INF 0x7fffffff
#define esp 1e-15
using namespace std;
const int maxn=1e9+10;
long long n,k;
double a[maxn],b[maxn];
double Dinkelbach(double L){
    double y[maxn], suma,sumb , minu;
    bool vis[maxn] ;
    int i , j , index;
    memset(vis,false,sizeof(vis));
    suma = sumb =0;
    for(i = 1; i <=n ;i++)y[i] = a[i] - L*b[i];
    for(i = 1;i <=n-k ; i++){
        minu = -INF;
        for(j = 1;j <=n ;j++){
            if(!vis[j]&&y[j] >minu){
                index = j;
                minu = y[j];
            }
        }
        vis[index] = true;
        suma+=a[index];sumb+=b[index];
    }
    return suma/sumb;
}
int main(){
    while(~scanf("%lld%lld",&n,&k),n|k){
        for(int i=0;i<n;i++)
            scanf("%lf",&a[i]);
        for(int i=0;i<n;i++)
            scanf("lf",&b[i]);
        double L1,L2;
        L1=0;
        while(1){
            L2=Dinkelbach(L1);
            if(L1==L2)break;
            L1=L2;
        }
        printf("%.0lf\n",L1*100);
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注