牛客暑假多校第五场A.gpa

一、题意

　　给出你的N门课程的考试成绩和所占的机电数目。允许你放弃K门课的成绩，要求你的平均学分绩最高能达到多少。

Kanade selected n courses in the university. The academic credit of the i-th course is s[i] and the score of the i-th course is c[i].

At the university where she attended, the final score of her is $\frac{\sum s[i]c[i]}{\sum s[i]}$

Now she can delete at most k courses and she want to know what the highest final score that can get.

二、题解

　　对于这道题直观的思路就是“猜一个目标学分绩点”之后验证在抛弃k门课的基础上，是否可以达到目标学分绩点。

　　对于每个目标学分绩点，对所有成绩进行一轮排序使得：拉低给定平均学分绩点最多的科目排在最前面，拉高给定平均学分绩点的成绩排在最后面。

　　则，该思路可以规避一些比较难想的复杂操作。

#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define veci vector<int>

const int MAXN=;

const double EXP = 1e-;

double sum_credit;

double sum_mul;

double target_gread;

double arr[MAXN];

double brr[MAXN];

int courses[MAXN];

int n,k;

bool cmp_tar(int a,int b)

{

    double tmpa = (target_gread *(sum_credit - arr[a]) + brr[a]*arr[a])/sum_credit - target_gread;

    double tmpb = (target_gread * (sum_credit - arr[b]) + brr[b]*arr[b])/sum_credit - target_gread;

    return tmpa < tmpb;

}

bool check(double target)

{

    target_gread = target;

    sort(courses,courses+n,cmp_tar);

        // cout<<"seq1: ";

        // for(int i=0;i<n;++i)

        //     cout<<arr[courses[i]]<<" ";

        // cout<<endl<<"seq2: ";

        // for(int i=0;i<n;++i)

        //     cout<<brr[courses[i]]<<" ";

        // cout<<endl;

    double ans = ;

    double summ = ;

    for(int i=min(k,n-);i<n;++i)

    {

            // cout<<"arr: "<<arr[courses[i]]<<" brr: "<<brr[courses[i]]<<endl;

        ans += arr[courses[i]] * brr[courses[i]];

        summ += arr[courses[i]];

    }

// cout<<"check: "<<target<<" "<<ans<<" "<<summ<<endl;

    ans /= summ;

    return ans>=target;

}

double bin_search(double a,double b)

{

        // cout<<a<<" : "<<b<<endl;

    if(abs(a-b)<=EXP)

        return a;

    double mid = (a+b)/;

    if(check(mid))return bin_search(mid,b);

    else return bin_search(a,mid);

}

void init()

{

    sum_credit = sum_mul = ;

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

        scanf("%lf",&arr[i]);

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

    {

        sum_credit += arr[i];

        scanf("%lf",&brr[i]);

        sum_mul += arr[i]*brr[i];

        courses[i] = i;

    }

    printf("%.6lf\n",bin_search(,));

}

int main(){

    cin>>n>>k;

    init();

    return ;

}

巴特西

牛客暑假多校第五场A.gpa

一、题意

二、题解

最新文章

热门文章