题解：P11462 huaijiao 要加学

原题链接

• 洛谷 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;
}