POJ 2976 매개변수 검색

Dropping tests
Time Limit: 1000MS
 
Memory Limit: 65536K
Total Submissions: 3042
 
Accepted: 964
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

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).
Source
Stanford Local 2005
 
제목 의 뜻 이 매우 명백하니, 너 에게 n 하나 를 줄게 k
그리고 두 줄의 수를 입력하여 각각 a1, a2, a3이라고 가정하면...an 및 b1, b2, b3...bn
그러면 r=sigma(ai)/sigma(bi)를 가정하면 지금 우리는 k대(ai,bi)를 버리고 r의 값을 최대로 할 수 있다
예를 들어
3 1 50 2 5 1 6 시 버릴 수 있습니다 (2,6)
따라서 r=(5+0)/(5+1) = 83.33333%
반올림
 
생각:
우리는 우선 그 가장 큰 r를 하나의 값으로 가정할 수 있다
그러면 100*sigma(a[i])/sigma(b[i])=r
변화: 100*sigma(a[i])-r*sigma(b[i])=0
------------------->sigma(100*a[i]-r*b[i])=0
아주 전형적인 단조 함수!!!2점 찾기로 풀 수 있어요.
먼저 100*a[i]-r*b[i]로 정렬한 다음에 앞의 n-k 개수를 선택한 다음에 화합을 구할 수 있습니다. 만약sum>0이면 l=mid
반대로 r=mid(순환 횟수도 반드시 >=15, 내가 먼저 쓴 10은 정밀도가 높지 않아서wa를 한 번 썼다)
 
내 코드:

#include<stdio.h>
#include<algorithm>

using namespace std;

struct node
{
	double a;
	double b;
	double x;
};
node in[1005];

bool cmp(node p,node t)
{
	return p.x>t.x;
}

int main()
{
	int n,k,i;
	double l,r,sum,mid;
	int time;
	while(scanf("%d%d",&n,&k)!=EOF)
	{
		if(n==0&&k==0)
			break;
		time=15;
		for(i=0;i<n;i++)
			scanf("%lf",&in[i].a);
		for(i=0;i<n;i++)
			scanf("%lf",&in[i].b);
		l=0;
		r=100;
		while(time--)
		{
			sum=0;
			mid=(l+r)/2;
			for(i=0;i<n;i++)
				in[i].x=100*in[i].a-mid*in[i].b;
			sort(in,in+n,cmp);
			for(i=0;i<n-k;i++)
				sum=sum+(100*in[i].a-mid*in[i].b);
			if(sum>0)
				l=mid;
			else
				r=mid;
		}
		printf("%.0lf/n",mid);
	}
	return 0;
}

 
천부적인 재능은 없고 부지런함만 있다!!