Dropping tests
题目链接:http://poj.org/problem?id=2976
Time Limit: 1000MS | Memory Limit: 65536K | |
Total Submissions: 20830 | Accepted: 7052 |
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 npositive 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).
题目大意:输入N K 下面有两行 每行有N个数 第一行代表N个a[i] 第二行代表N个b[i] 问你按照上面的公式算 去掉K个 得到的最大结果是多少
思路:自己并没有想到怎么二分 ,自己想到的是怎么贪心,但是感觉不行,就没去尝试了,其实想的到二分答案,但是怎么判断答案是否成立就没有想到了,这里用到的一种思想,分析表达式
以前我都是看到表达式就看一下的,从来没有给它仔细化简分析啥的 这一题算是一个教训吧! 那么下面看一下这个表达式到底怎么回事
令r = ∑a[i] * x[i] / (b[i] * x[i]) 则必然∑a[i] * x[i] - ∑b[i] * x[i] * r= 0;(条件1)并且任意的 ∑a[i] * x[i] - ∑b[i] * x[i] * max(r) <= 0 (条件2,只有当∑a[i] * x[i] / (b[i] * x[i]) = max(r) 条件2中等号才成立)然后就可以枚举r , 对枚举的r, 求Q(r) = ∑a[i] * x[i] - ∑b[i] * x[i] * r 的最大值, 为什么要求最大值呢? 因为我们之前知道了条件2,所以当我们枚举到r为max(r)的值时,显然对于所有的情况Q(r)都会小于等于0,并且Q(r)的最大值一定是0.而我们求最大值的目的就是寻找Q(r)=0的可能性,这样就满足了条件1,最后就是枚举使得Q(r)恰好等于0时就找到了max(r)。而如果能Q(r)>0 说明该r值是偏小的,并且可能存在Q(r)=0,而Q(r)<0的话,很明显是r值偏大的,因为max(r)都是使Q(r)最大值为0,说明不可能存在Q(r)=0了。
注意:二分真的很气人啊,这题用了以前经常用的二分板子,竟然错了。。。 真的不明白为啥,就是二分最后的结果是l 还是r 应该是这题有点问题,下面wa的代码也给出来吧
wa的:
#include<iostream>
#include<algorithm>
#include<stdio.h>
using namespace std;
typedef long long ll;
const int maxn=+;
const double inf=1e15;
const double eps=1e-;
int N,K;
ll a[maxn],b[maxn];
double c[maxn];
bool cmp(const double x,const double y)
{
return x>y;
}
bool judge(double mid)
{
for(int i=;i<N;i++)//找到最优的解
{
c[i]=a[i]-mid*b[i];
}
sort(c,c+N,cmp);
double sum=;
for(int i=;i<N-K;i++) sum+=c[i];
return sum>=;
}
int main()
{
while(cin>>N>>K)
{
if(N==&&K==) break;
for(int i=;i<N;i++) cin>>a[i];
for(int i=;i<N;i++) cin>>b[i];
double l=,r=inf;
double ans; while(r-l>=eps)
{
double mid=(r+l)/;
//cout<<mid<<endl;
if(judge(mid))
{
ans=mid;
l=mid+eps;
}
else r=mid;
//cout<<"ans: "<<ans<<endl;
//cout<<"l: "<<l<<endl;
//cout<<"r: "<<r<<endl;
}
printf("%.0lf\n", ans * ); /*
double mid;
while(r-l>=eps)
{ mid=(l+r)/2;
if(judge(mid))
l=mid;
else r=mid;
cout<<"l: "<<l<<endl;
cout<<"r: "<<r<<endl;
}
printf("%.0lf\n",r*100);
//printf("%.0lf\n", ans * 100);
//cout<<(int)(ans*100+0.5)<<endl;
*/
}
return ;
} /*
*/
ac的:
#include<iostream>
#include<algorithm>
#include<stdio.h>
using namespace std;
typedef long long ll;
const int maxn=+;
const double inf=1e15;
const double eps=1e-;
int N,K;
ll a[maxn],b[maxn];
double c[maxn];
bool cmp(const double x,const double y)
{
return x>y;
}
bool judge(double mid)
{
for(int i=;i<N;i++)//找到最优的解
{
c[i]=a[i]-mid*b[i];
}
sort(c,c+N,cmp);
double sum=;
for(int i=;i<N-K;i++) sum+=c[i];
return sum>=;
}
int main()
{
while(cin>>N>>K)
{
if(N==&&K==) break;
for(int i=;i<N;i++) cin>>a[i];
for(int i=;i<N;i++) cin>>b[i];
double l=,r=inf;
double ans; while(r-l>=eps)
{
double mid=(r+l)/;
//cout<<mid<<endl;
if(judge(mid))
{
ans=mid;
l=mid+eps;
}
else r=mid;
//cout<<"ans: "<<ans<<endl;
//cout<<"l: "<<l<<endl;
//cout<<"r: "<<r<<endl;
}
printf("%.0lf\n", r * ); /*
double mid;
while(r-l>=eps)
{ mid=(l+r)/2;
if(judge(mid))
l=mid;
else r=mid;
cout<<"l: "<<l<<endl;
cout<<"r: "<<r<<endl;
}
printf("%.0lf\n",r*100);
//printf("%.0lf\n", ans * 100);
//cout<<(int)(ans*100+0.5)<<endl;
*/
}
return ;
} /*
*/
最新文章
- CloudSim介绍和使用
- 两个实用的方法从Base64字符串生成RSAPublicKey及RSAPrivatekey
- 运行python代码报错UnicodeDecodeError: &#39;ascii&#39; codec can&#39;t decode byte 0xe7 in position 91: ordinal not in range(128)的解决办法
- 打包程序tar
- 九度OJ 1510 替换空格
- Java I/O重定向
- 怎么样删除eclipse已经记录svn的地址
- 数据结构(线段树):BZOJ 1018: [SHOI2008]堵塞的交通traffic
- Struts2学习笔记(一):Struts2开发环境的配置
- 执行此安装程序之前,必须安装 32 位 Windows 映像处理组件(WIC)解决的方法
- Web网页中内嵌Activex的Activex插件开发 .
- 改ext界面
- 201521123096《Java程序设计》第五周学习总结
- 【读书笔记】iOS-优化内存
- linux服务器中Jenkins集成git、Gradle持续构建Springboot项目
- [SoapUI] Property Expansion in soapUI
- spring cloud学习(四) 动态路由
- Linux服务器---配置apache支持用户认证
- 【洛谷】【线段树】P3353 在你窗外闪耀的星星
- 20165329 Java实验二:面向对象编程