题意: 有 n 场考试, 给出每场答对的题数 a 和这场一共有几道题 b, 求去掉 k 场考试后, 公式 . 的最大值
解题关键: 01 分数规划, double 类型二分的写法 (poj 崩溃, 未提交)
或者 r-l<=1e-3(右边是精度)
- #include<cstdio>
- #include<cstring>
- #include<algorithm>
- #include<cstdlib>
- #include<iostream>
- #include<cmath>
- #define maxn 1002
- #define eps 1e-8
- using namespace std;
- typedef long long ll;
- int n,k;
- double ans;
- struct node{
- int a,b;
- }num[maxn];
- bool cmp(node &x,node &y){
- return x.a-x.b*ans>y.a-y.b*ans;
- }
- bool check(double x){
- ans=x;
- sort(num+1,num+n+1,cmp);
- double sum=0;
- for(int i=1;i<=n-k;i++) sum+=num[i].a-x*num[i].b;
- return sum>=-eps;
- }
- double erfen(double l,double r){
- for(int i=1;i<=1000;i++){
- double mid=(l+r)/2;
- if(check(mid)) l=mid;
- else r=mid;
- }
- return r;
- }
- int main(){
- while(cin>>n>>k){
- if(!n&&!k) break;
- for(int i=1;i<=n;i++) cin>>num[i].a;
- for(int i=1;i<=n;i++) cin>>num[i].b;
- double ans=erfen(0,1.0*(ll)100000000000);
- cout<<(int)(100*ans)<<"\n";
- //printf("%d\n",(int)ans);
- }
- return 0;
- }
- [poj2976]Dropping tests(01 分数规划, 转化为二分解决)
来源: http://www.bubuko.com/infodetail-2945761.html