\(\text{Problem}:\)题目链接
\(\text{Solution}:\)
贪心的想法是，对于选取 \(p\) 个杯子，总容积固定时，选取的杯子初始装的总水量最大。正确性显然（\(x+\cfrac{y}{2}\geq x-p+\cfrac{y+p}{2}\)）。
设 \(F_{i,j,k}\) 表示前 \(i\) 个杯子中，选了 \(j\) 个杯子，这 \(j\) 个杯子的总容积为 \(k\) 时，最大的初始总水量。对于每个 \(p\)，枚举总容积 \(k\)，那么答案为 \(\min\{k,F_{n,p,k}+\cfrac{sum-F_{n,p,k}}{2}\}\)，\(sum\) 表示所有杯子的总水量。对于这些答案取 \(\max\) 即得到最终的答案。将 \(a_{i},b_{i}\) 看作与 \(n\) 同阶，时间复杂度为 \(O(n^4)\)，且常数极小，可以通过本题。
\(\text{Code}:\)
#include <bits/stdc++.h>
#pragma GCC optimize(3)
#define int long long
#define ri register
#define mk make_pair
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define is insert
#define es erase
using namespace std; const int N=110;
inline int read()
{
int s=0, w=1; ri char ch=getchar();
while(ch<'0'||ch>'9') { if(ch=='-') w=-1; ch=getchar(); }
while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+(ch^48), ch=getchar();
return s*w;
}
int n,a[N],b[N],sum,tot,F[N][N*N];
signed main()
{
n=read();
for(ri int i=1;i<=n;i++) a[i]=read(), b[i]=read();
memset(F,-0x3f,sizeof(F)), F[0][0]=0;
for(ri int i=1;i<=n;i++)
{
sum+=b[i];
tot+=a[i];
for(ri int j=tot;j>=a[i];j--)
{
for(ri int k=i;k;k--)
{
F[k][j]=max(F[k][j],F[k-1][j-a[i]]+b[i]);
}
}
}
for(ri int i=1;i<=n;i++)
{
double mx=0;
for(ri int j=1;j<=tot;j++)
{
mx=max(mx,min(1.0*j,1.0*F[i][j]+0.5*(sum-F[i][j])));
}
printf("%.10lf ",mx);
}
puts("");
return 0;
}