CF2023D Many Games 题解

非常像我会做的题目。要是我打 CF 的时候不去吃完饭，不打摆感觉还是非常有机会做出来的。

首先考虑什么样的物品才能使答案增大。不妨设当前的 $\prod\limits_i {p_i\over 100} = X,\sum\limits_i w_i = Y$。

$\begin{aligned} XY <& X {p_i \over 100} (Y+w_x)\\ Y <& {p_i \over 100} (Y+w_x)\\ Y <& {p_i \over 100} Y+{p_i \over 100}w_x\\ (1-{p_i \over 100})Y <& {p_i \over 100}w_x\\ Y <& {{p_i \over 100}w_x \over (1-{p_i \over 100})}\\ Y <& {p_i \cdot w_x \over (100-p_i)}\\ \end{aligned}$

所以我们得出结论当当前重量大于 $2.1 \cdot 10^5$ 左右时必然不会有新增的物品。（赛时怎么到这里就直接莽上去了qwq）。

如果你按照 $p_i$ 分组，按照 $w_i$ 从大到小排序的话，我们每次一定是取一段前缀。猜想这个前缀的长度并不长，原因也比较简单，就是考虑当前加进去 $w$ 要更优。

$\begin{aligned} p^k \cdot W &< p^{k+1} \cdot (W+minw) \\ &\leq p^{k+1} \cdot W {k+1\over k} \\ p &> {k+1 \over k} \\ kp & > k+1\\ k & > {1\over p-1} \\ k & < {100 \over 100 - p_i} \\ \end{aligned}$

所以你照着取一起下物品总数是极少的。最后你直接做一个背包就行了。

// Problem: Many Games
// URL: https://www.luogu.com.cn/problem/CF2023D
// Writer: WRuperD
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
const long long inf = 1e18;
const int mininf = 1e9 + 7;
#define int long long
#define pb emplace_back
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
inline void write(int x){if(x<0){x=~(x-1);putchar('-');}if(x>9)write(x/10);putchar(x%10+'0');}
#define put() putchar(' ')
#define endl puts("")
const int MAX = 21e4 + 10;
double f[MAX];

priority_queue <int> que[MAX];

void solve(){
	int n = read();
	double preans = 0;
	for(int i = 1; i <= n; i++){
		int p = read(), w = read();
		if(p == 100){
			preans += w;
		}else{
			que[p].push(w);
		}
	}
	f[0] = 1.0;
	for(int i = 1; i <= 99; i++){
		int lim = 100 / (100 - i) + 1;
		while(!que[i].empty() and lim--){
			int u = que[i].top();
			que[i].pop();
			for(int j = MAX - 10; j >= u; j--){
				f[j] = max(f[j], f[j - u] * (double)(i) / 100.0);
			}
		}
	}
	double ans = 0;
	for(int i = 0; i < MAX; i++){
		ans = max(ans, double(i + preans) * f[i]);	
	}
	printf("%.7f\n", ans);
}

signed main(){
	int t = 1;
	while(t--)	solve();
	return 0;
}