自动搬运

查看原文

来自洛谷，原作者为

	封禁用户 None

搬运于2025-08-24 22:36:30，当前版本为作者最后更新于2022-11-13 17:14:15，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

容易想到一个错误的贪心：

• 一定要先得到支持者，再和支持者一起演讲。

• 集中力量办事效率高，支持者们和本人一定要在同一个州进行演讲。

• 按 $b_i$ 从小到大排序，再将剩下的按 $a_i$ 从小到大排序，算出最小值。

但这个贪心有一个问题：可能一些选中的 $b_i$ 对应的 $a_i$ 极其地小。

明确一个问题，我们不选 $b_i$ 的原因是因为 $a_i$ 更加优秀。

我们修改贪心策略，需要加入一些动态规划：

• 按 $b_i$ 从小到大排序。

• 枚举 $i$,对于前 $i$ 个，肯定是要么选 $a_i$，要么选 $b_i$，后面的肯定选 $a_i$ 最小的 $k-i$ 个。

代码也就呼之欲出了：

#include <bits/stdc++.h>
using namespace std;
template<typename T>inline void read(register T &x)
{
	register T p = 1,num = 0;
	char c = getchar();
	while(c < '0'||c > '9')
	{
		if(c == '-') p = -1;
		c = getchar();
	}
	while('0' <= c&&c <= '9')
	{
		num = (num<<3)+(num<<1)+(c^48);
		c = getchar();
	}
	x = p * num;
}
#define F(i,a,b) for(register int i=a;i<=b;++i)
#define D(i,a,b) for(register int i=a;i>=b;--i)
#define N 510
struct node
{
	double a,b;
	inline bool friend operator<(node X,node Y)
	{
		return X.b < Y.b;
	}
}p[N],q[N];
double dp[N][N],sum[N][N];
inline bool cmp(node X,node Y)
{
	return X.a < Y.a;
}
int n,k;
int main()
{
	read(n),read(k);
	F(i,1,n) 
	{
		scanf("%lf%lf",&p[i].a,&p[i].b);
		if(p[i].b == -1) p[i].b = 1e18;	
	}
	sort(&p[1],&p[n+1]); 
	D(i,n,1)
	{
		F(i,1,n) q[i] = p[i];
		sort(&q[i],&q[n+1],cmp);
		F(j,1,n-i+1) sum[i][j] = sum[i][j-1] + q[i+j-1].a;
	} 
	double ans = 1e18;
	F(cas,0,n)
	{
		memset(dp,0x7f,sizeof(dp));	
		dp[0][0] = 0.0;
		F(i,1,n)
			F(j,0,cas)
			{
				dp[i][j] = min(dp[i][j],dp[i-1][j] + p[i].a / (cas + 1));
				if(j&&p[i].b != 1e18) dp[i][j] = min(dp[i][j],dp[i-1][j-1] + p[i].b / j);	
			}
		F(i,cas,n) ans = min(ans,dp[i][cas] + sum[i+1][k-i] / (cas + 1));
	}
	printf("%.15lf",ans);
	return 0;
}