题解：P11462 huaijiao 要加学

· · 题解

解题思路

整理：

\begin{aligned} W &= \sum_{i=1}^n(w_i\times c_i) \\ &= \sum_{i=1}^n\left(\min\left(1,\frac{x_i}{k_i}\right)\times 100\times c_i\right) \\ &= 100\sum_{i=1}^n\left(\min(k_i,x_i )\times \frac{c_i}{k_i}\right) \end{aligned}

可以发现，第 i 门课程每学一天的收益是 \frac{c_i}{k_i}，且最多可学 k_i 天。为了最大化总收益，应优先选择收益较高的课程。

因此，可以按 \frac{c_i}{k_i} 从大到小排序，然后贪心地选择每门课程最多学习 x = \min(k_i, m) 天，并更新剩余天数 m \gets m - x。

参考代码

#include <bits/stdc++.h>
using namespace std;

using ll=long long;
const int N=1005;
struct Node
{
    int c,k;
}a[N];
bool cmp(const Node &u,const Node &v)
{
    return u.c*v.k>v.c*u.k;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i].c;
    for(int i=1;i<=n;i++)cin>>a[i].k;
    sort(a+1,a+n+1,cmp);
    double ans=0;
    for(int i=1;i<=n;i++)
    {
        int x=min(m,a[i].k);
        ans+=x*100.0/a[i].k*a[i].c;
        m-=x;
    }
    cout<<fixed<<setprecision(4)<<ans<<'\n';
    return 0;
}