Hack 【二分答案】

题意：给出n门课程，每一门课程考的分数，每一门课程的学分，求最多删去k组数据之后能够得到的最大加权平均数

先开一个数组x[],其中x[i]=1代表没有删除这门课程，x[i]=0表示删除了这门课程

然后p[i]=R*c[i]-c[i]*s[i]=c[i]*(R-s[i])

又因为满分为100分，就在0.0在100.0二分来找再将p数组降序排列，ans为其前n-k个数的和，如果ans-0>eps,那么l=mid, 如果ans-0<eps,那么r=mid

因为p[]数组是按照降序排列的，所以ans应该是递减的，大概是像这幅图一样

貌似这样理解有问题，再想一想先-----

下面是学习的代码---------------

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include <cmath>

 #include<stack>

 #include<vector>

 #include<map>

 #include<set>

 #include<queue>

 #include<algorithm>

 using namespace std;

 typedef long long LL;

 const int INF = (<<)-;

 const int mod=;

 const int maxn=;

 double eps=1e-;

 int s[maxn],c[maxn];

 double p[maxn];

 bool cmp(double a,double b){

     return a>b;

 }

 int main(){

     int ncase;

 //    freopen("in.txt","r",stdin);

 //    freopen("out.txt","w",stdout);

     scanf("%d",&ncase);

     for(int t=;t<=ncase;t++){

         int n,k;

         scanf("%d %d",&n,&k);

         for(int i=;i<=n;i++) scanf("%d",&s[i]);

         for(int i=;i<=n;i++) scanf("%d",&c[i]);

         double l=0.0,r=100.0,mid;

         while((r-l)>eps){

              mid=(l+r)/;

             for(int i=;i<=n;i++) p[i]=(double)c[i]*(double)(s[i]-mid);

             sort(p+,p+n+,cmp);

             double ans=0.0;

             for(int i=n-k;i>=;i--) ans+=p[i];

             if(ans->eps) l=mid;

             else r=mid;

         }

         printf("Case #%d:\n",t);

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

     }

     return ;

 }

巴特西

Hack 【二分答案】

最新文章

热门文章