poj2976

maksyuki 发表于 oj 分类，标签: 数值-二分\三分\折半枚举

29 1月 2016

Dropping tests

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_i for 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

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

Sample Output

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

题目类型：最大化平均值(二分)

算法分析：原问题可以转化为求解”单位价值大于等于x”的最大的x。则每次判断是否满足拿n-k的物品使得vi-x*wi大于等于0，当然这里要贪心地拿最高的k个

/*************************************************
Author        :supermaker
Created Time  :2016/1/29 12:47:33
File Location :C:\Users\abcd\Desktop\TheEternalPoet
**************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")
#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)
#define CPPFF ifstream cin ("aaa.txt")
#define	DB(ccc)	cout << #ccc << " = " << ccc << endl
#define PB push_back
#define MP(A, B) make_pair(A, B)

typedef long long LL;
typedef unsigned long long ULL;
typedef double DB;
typedef pair <int, int> PII;
typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int maxn = 1e3 + 66;

int v[maxn], w[maxn], n, k;
double aa[maxn];

int sgn (double val)
{
	if (fabs (val) < EPS) return 0;
	else if (val < 0) return -1;
	return 1;
}

bool TT (double x)
{
	for (int i = 1; i <= n; i++)
		aa[i] = v[i] - x * w[i];
	sort (aa + 1, aa + 1 + n, greater <double> ()); 

	double res = 0;
	for (int i = 1; i <= n && i <= n - k; i++)
		res += aa[i];
	
	if (sgn (res) >= 0) return true;
	return false;
}

int main()
{
    //CFF;
    //CPPFF;
	while (scanf ("%d%d", &n, &k) != EOF)
	{
		if (n == 0 && k == 0) break;
		for (int i = 1; i <= n; i++)
			scanf ("%d", &v[i]);

		for (int i = 1; i <= n; i++)
			scanf ("%d", &w[i]);
	
		double low = 0, high = 6e16, mid;
		int tot = 1;
		while (tot <= 100)
		{
			mid = (low + high) / 2.0; 
			if (TT (mid)) low = mid;
			else high = mid;
			tot++;
		}

		printf ("%.lf\n", mid * 100);
	}
    return 0;
}

100

101

102

103

104

105

106

/*************************************************

Author :supermaker

Created Time :2016/1/29 12:47:33

File Location :C:\Users\abcd\Desktop\TheEternalPoet

**************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)

#define CPPFF ifstream cin ("aaa.txt")

#define DB(ccc) cout << #ccc << " = " << ccc << endl

#define PB push_back

#define MP(A, B) make_pair(A, B)

typedef long long LL;

typedef unsigned long long ULL;

typedef double DB;

typedef pair <int, int> PII;

typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 1e3 + 66;

int v[maxn], w[maxn], n, k;

double aa[maxn];

int sgn (double val)

{

if (fabs (val) < EPS) return 0;

else if (val < 0) return -1;

return 1;

}

bool TT (double x)

{

for (int i = 1; i <= n; i++)

aa[i] = v[i] - x * w[i];

sort (aa + 1, aa + 1 + n, greater <double> ());

double res = 0;

for (int i = 1; i <= n && i <= n - k; i++)

res += aa[i];

if (sgn (res) >= 0) return true;

return false;

}

int main()

{

//CFF;

//CPPFF;

while (scanf ("%d%d", &n, &k) != EOF)

{

if (n == 0 && k == 0) break;

for (int i = 1; i <= n; i++)

scanf ("%d", &v[i]);

for (int i = 1; i <= n; i++)

scanf ("%d", &w[i]);

double low = 0, high = 6e16, mid;

int tot = 1;

while (tot <= 100)

{

mid = (low + high) / 2.0;

if (TT (mid)) low = mid;

else high = mid;

tot++;

}

printf ("%.lf\n", mid * 100);

}

return 0;

}

poj2954

poj3111

一	二	三	四	五	六	日
« 6月
						1
2	3	4	5	6	7	8
9	10	11	12	13	14	15
16	17	18	19	20	21	22
23	24	25	26	27	28	29
30	31

超客的水墨烟雨

poj2976

分类目录

标签云

书签

近期评论