Problem 1203 - put on make up
Problem 1203 - put on make up
Time Limit: 3000MS Memory Limit: 65536KB Difficulty:
Total Submit: 6 Accepted: 2 Special Judge: No
Description
作为coser，化妆是很重要的。于是呢，每次出外景都要求妆娘的行为是不对的（哪里有那么多免费的妆娘让你用呀），所以要自己学啦。那么，要学的话，得先买化妆品对吧~对吧对吧~
于是很欢乐地背着包出去，结果更欢乐地发现了，那个，包，它，有点小了><所以不得不对要买的东西做个规划。
姐姐我现在看上了n种化妆品，但是由于那可怜的小包咱只能买k种，于是我给每个化妆品两个评价标准a和b，现在我希望买的k种化妆品使得ln(a1*a2*…*ak)/ln(b1*b2*…*bk)最大。于是你只要能帮姐姐我算出这个最大值就可以了喵，至于为什么要取ln，只是因为我觉得e是一个比较好玩的数字而已。
Input
多组数据以EOF结束。每组数据第一行包括两个数n和k，接下来两行各有n个数，第一行是每个化妆品对应的评价标准ai，第二行是bi，输入均为整数。
0<k<=n<=10000 10<=bi<=ai<=1000
Output
每组数据输出一行为对应数据的最大值，保留三位有效数字。
Sample Input
3 2
60 50 40
10 20 30
Sample Output
1.511
Hint
Source
d891320478
分析Time Limit: 3000MS Memory Limit: 65536KB Difficulty:
Total Submit: 6 Accepted: 2 Special Judge: No
Description
作为coser，化妆是很重要的。于是呢，每次出外景都要求妆娘的行为是不对的（哪里有那么多免费的妆娘让你用呀），所以要自己学啦。那么，要学的话，得先买化妆品对吧~对吧对吧~
于是很欢乐地背着包出去，结果更欢乐地发现了，那个，包，它，有点小了><所以不得不对要买的东西做个规划。
姐姐我现在看上了n种化妆品，但是由于那可怜的小包咱只能买k种，于是我给每个化妆品两个评价标准a和b，现在我希望买的k种化妆品使得ln(a1*a2*…*ak)/ln(b1*b2*…*bk)最大。于是你只要能帮姐姐我算出这个最大值就可以了喵，至于为什么要取ln，只是因为我觉得e是一个比较好玩的数字而已。
Input
多组数据以EOF结束。每组数据第一行包括两个数n和k，接下来两行各有n个数，第一行是每个化妆品对应的评价标准ai，第二行是bi，输入均为整数。
0<k<=n<=10000 10<=bi<=ai<=1000
Output
每组数据输出一行为对应数据的最大值，保留三位有效数字。
Sample Input
3 2
60 50 40
10 20 30
Sample Output
1.511
Hint
Source
d891320478
我怀着忐忑的心情决定尝试贪心算法，还好AC了。
如果在前i个值中选k个得到的最大值为F[i, k]。那么F[i + 1, k] 等于用第i+1个元素替换原k个元素之一得到的最大值。
如果在前i个值中选k个得到的最大值为F[i, k]。那么F[i + 1, k] 等于用第i+1个元素替换原k个元素之一得到的最大值。
程序代码：#include<stdio.h>
#include<math.h>
int main()
{
double ln[1001], a[10000], b[10000], ra, rb, mr, tr;
int n, k, mi, i, j;
for(i = 10; i <= 1000; i++) ln[i] = log(i);
for(; scanf("%d%d", &n, &k) != EOF; printf("%.3lf\n", mr))
{
for(i = 0; i < n; a[i++] = ln[j]) scanf("%d", &j);
for(i = 0; i < n; b[i++] = ln[j]) scanf("%d", &j);
for(ra = rb = i = 0; i < k; i++) ra += a[i], rb += b[i];
for(mr = ra / rb; i < n; ra -= a[mi], a[mi] = a[i], rb -= b[mi], b[mi] = b[i], i++)
for(ra += a[i], rb += b[i], mi = i, j = 0; j < k; j++)
if((tr = (ra - a[j]) / (rb - b[j])) > mr) mr = tr, mi = j;
}
return 0;
}
重剑无锋，大巧不工
