【POJ 2976 Dropping tests】

时间:2023-12-29 14:55:50

Time Limit: 1000MS
Memory Limit: 65536K

Total Submissions: 13849
Accepted: 4851

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

【POJ 2976 Dropping tests】.

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 【POJ 2976 Dropping tests】. However, if you drop the third test, your cumulative average becomes 【POJ 2976 Dropping tests】.

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 ≤ aibi ≤ 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

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,选择n-k个元素,询问【POJ 2976 Dropping tests】的最大值。

题解:

        ①题目要求求出Sigma式子的最大值,可以考虑单个式子ai/bi的最大值,然后将它们合起来。

        ②但是直接计算是不方便转化的,因为Sigma和单个式子还是有区别的。

        ③由于具有取值上的单调性,因此考虑二分,二分最大值x,那么则有:

                 ∑ai/∑bi>=x      移项得到:   ∑ai>=x*∑bi ——> ∑ai-x*∑bi>=0

        ④所以就二分啊,使得x不断变大,大到使得∑ai-x*∑bi几乎等于0,就是最有解了。

#include<stdio.h>
#include<algorithm>
#define go(i,a,b) for(int i=a;i<=b;i++)
#define ro(i,a,b) for(int i=a;i>=b;i--)
int n,k,a[4001],b[4001];
double T[4001],res,l,r,M;
bool check(double x)
{
go(i,1,n)T[i]=a[i]-x*b[i];std::sort(T+1,T+1+n);res=0;
go(i,k+1,n)res+=T[i];return res>=0;
}
int main()
{
while(scanf("%d%d",&n,&k),n|k)
{
go(i,1,n)scanf("%d",a+i);l=0;
go(i,1,n)scanf("%d",b+i);r=1;
while(r-l>1e-6)M=(l+r)/2,check(M)?l=M:r=M;printf("%.0f\n",l*100);
}
}//Paul_Gudeiran

 

希望你把我记住你流浪的孩子,无论在何时何地我都想念着你。————汪峰《我爱你中国》