自动搬运

查看原文

来自洛谷，原作者为

	Hexarhy 干好饭，睡好觉，遇见好人。

搬运于2025-08-24 21:26:35，当前版本为作者最后更新于2019-08-07 00:28:55，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

好久没有写二分答案了，来复习复习。顺便补充个像样的有$\LaTeX$的题解。

---

刚开始看到题目还以为是01背包，但却是求平均值最大，故不考虑。

但是不好思考呢……那先从式子入手：

假设存在一种最优解$ans$，则

$$\large ans=\frac{\sum^m_{i=1}v_i}{\sum^m_{i=1}c_i} $$

式子太复杂？尝试化一下。

$$\text{去分母得，}\sum^m_{i=1}c_i·ans=\sum^m_{i=1}v_i$$ $$\text{移项得，}\sum^m_{i=1}c_i·ans-\sum^m_{i=1}v_i=0$$

---

观察式子，不难发现最优解$ans$会使得左边$=0$，因此我们的目标就是尽可能地的靠近$0$。加上$ans$具有单调性，这时就考虑到二分。

check()也就很好写了。由于我们想让左边尽可能$<0$，则考虑贪心，排序并选前$m$个最小的权值并得到之和$tot$。

此时要对check()得到的$tot$进行分类讨论了：

• 当$tot<0$时，说明$ans$还能再大一点，故二分时$l=mid$，往右靠。

• 当$tot>0$时，说明$ans$还能再小一点，故二分时$r=mid$，往左靠。

• 当$tot=0$时，就是答案了，可以直接结束二分。

另外，由于有小数，二分结束条件$l,r$之间就不是$r-l\ge 1$，而是形如$r-l\le 10^{-5}$保证精度。

---

时间复杂度：

• 输入：$\Theta(n)$

• 二分：$\Theta(\log\max\large\{\frac{v_i}{v_i}\})$

• 排序：$\Theta(n\log n)$

• 计数$tot$：$\Theta(m)$

综上所述，时间复杂度为：

$$\large\Theta(n+(m+n\log n)\log\max\{\frac{v_i}{v_i}\}) $$$$\large\approx\Theta(n\log n \log \max\{\frac{v_i}{v_i}\}) $$

最坏也不过达到大约$2\times 10^4$。

---

讲得很细了，代码注释就不给那么多了。分析里都有。

代码如下：

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

const int MAXN=500;
int n,m;
struct coffee
{
	int v,t;
	double avr;//算权值t*x-v
	bool operator<(const coffee a)const
	{
		return avr<a.avr;
	}
}a[MAXN];
double ans,l,r;


void input(void)
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	 cin>>a[i].v;
	for(int i=1;i<=n;i++)
 	 cin>>a[i].t;
}

bool check(const double x)
{
	for(int i=1;i<=n;i++)
	 a[i].avr=x*a[i].t-a[i].v;//算每个的权值
    sort(a+1,a+n+1);//从小到大排序
	double tot=0;
	for(int i=1;i<=m;i++)//取前m个小的
	 tot+=a[i].avr;
	return tot<=0;
}

void binary(void)
{
	for(int i=1;i<=n;i++)
	 if(a[i].v*1.0/a[i].t>r)
	  r=a[i].v*1.0/a[i].t;//算出上界
	while(r-l>1e-5)
	{
		const double mid=(l+r)/2.0;
		if(check(mid))//注意分类讨论（这里结合二分求上下界）
		 l=mid;
		else
		 r=mid;
	}
	ans=l;
}

int main()
{
	input();
	binary();
	printf("%.3f\n",ans);
	return 0;
}

---

还没结束呢！

现在仔细想想，或许可以不用二分（优势在于避免分类讨论和上下界问题），考虑枚举$x(x\in[0,\max\large\{\frac{v_i}{c_i}\}])$，并进行check()，好像也不会超时。理论时间复杂度：

$$\Theta(n\log n \max\{\frac{v_i}{c_i}\})$$

最坏情况大约为$1.5\times 10^8$。

但实际题目中除非专门卡否则一般达不到这样的复杂度，加上编译器的优化和lg评测机的良好性能，卡一卡（甚至不用）就能过去。

当然以上只是个人看法，作者还没实践过。

---

完结撒花！✿✿ヽ(°▽°)ノ✿