提交时间:2024-10-02 16:36:23
运行 ID: 32979
#include<bits/stdc++.h> using namespace std; int n,m,a[20010],i,k,j,lastk; bool cmp(int a,int b){ return a<b; }long double dp[2010][5010],ans,nxt[20010],nowans; queue<pair<int,int> > state; bool vis[2010][5010]; int main(){ //freopen("monster.in","r",stdin); //freopen("monster.out","w",stdout); //ios::sync_with_stdio(0); scanf("%d %d",&n,&m); //cout<<n<<m<<'\n'; for(int i=1;i<=n;i++){ scanf("%d",&a[i]); }sort(a+1,a+n+1,cmp); // for(int i=1;i<=n;i++){ // cout<<a[i]<<' '; for(int i=0;i<=n+1;i++){ for(int j=0;j<=m+1;j++){ dp[i][j]=1e9; } } dp[0][m]=ans=n; //cout<<ans<<'\n'; for(i=0;i<=n;i++){ for(j=1;j<=n;j++){ for(k=m-a[i];k>=a[i]*(n-j);k--){ nowans=((long double)(i)/(long double)n); lastk=k+a[i]; if(dp[j-1][lastk]==1e9) continue; dp[j][k]=min(dp[j-1][lastk]-nowans,dp[j][k]); ans=min(dp[j][k],ans); } } } printf("%.10Lf",ans); }