wls做了一個夢，夢里他擁有了超能力。
森林里有n棵樹，同時wls有兩種能力，兩種能力總共可以使用m次。

• 選擇一棵樹，將其從森林中刪除
• 選擇森林中的一棵樹，將它的高度提升1，但是每顆樹只能被提高k次，k次以后這個能力就對這棵樹失效了。
• 現(xiàn)在他想讓森林樹木高度的平均值盡可能的大。

輸入格式:

第一行n,k,m，含義同上，下一行，給出n棵樹木的初始高度
（所有數(shù)字均小于1e5）

輸出格式:

輸出最大的平均值，保留兩位小數(shù)。

輸入樣例:

2 4 6 4 7 4 2 6 1 3 2 3

輸出樣例:

11.00 5.00

感覺這類的題目挺有意思的，想出來挺有成就感的，在這里分享一下我的思路。

首先我們看到題目我剛開始想的是把小的都踢掉，然后對一個進行升高，但是很快就排除了因為有6 7這樣的例子，然后又想用兩個選擇去判斷，就是先對小的看是否要踢出他，判斷的依據(jù)是把他刪了的結(jié)果，然后給他加1的結(jié)果，但是這樣的例子顯然不行，因為如果有2 9000?99999，2，3，4的話這樣的題解就錯了，很明顯我們沒有看該過程對后面數(shù)據(jù)的影響，然后我就想動態(tài)規(guī)劃了，但是這10000個數(shù)據(jù)去動態(tài)規(guī)劃多少有點超時，所以我就想把所有精力集中到是否該刪除這個結(jié)點，此時我就想到了控制變量法了，如果我刪除這個剩下的操作都用+1，和這個不刪除都加1，如果前面的大我就把他刪了，因為我刪了之后可以更大，每一個都這樣去迭代，最終就得出了最優(yōu)解吧（應(yīng)該是的滑稽😆）?，根據(jù)這個我們寫出了下面的代碼。

#include <bits/stdc++.h> using namespace std; int main(){int n,m,k;scanf("%d%d%d",&n,&m,&k);int i;int a[n];double sum=0;for(i=0;i<n;i++){scanf("%d",&a[i]);sum=sum+a[i];}sum=sum/n;//平均值sort(a,a+n);//排好序int s;double lans,rans;//不刪除和刪除的結(jié)果int take=n*m;//忽略操作數(shù)，我能進行第一種操作的最大次數(shù)i=0;//該刪除的結(jié)點int temp=n-1;int t;while(k){s=min(k,n*m);//得到我能進行第一次操作的最大數(shù)lans=(double)s/n+sum;//不刪除的結(jié)果if(n-1>0){t=min(k-1,(n-1)*m);rans=(sum*n-a[i])/(n-1)+(double)t/(n-1);//刪除的結(jié)果}else rans=-1;//到了只有一個就只能加了。if(lans>rans){sum=sum+(double)s/n;break;}else {//刪除該結(jié)點之后的平均值，便于進行下一次操作sum=(sum*n-a[i])/(n-1);i++;//到達該刪除結(jié)點的坐標(biāo)n--;//人數(shù)少了一個}k--;//操作數(shù)減1}printf("%.2lf",sum);system("pause"); }

1000ms的用了7ms，今晚加雞腿。?

總結(jié)

以上是生活随笔為你收集整理的7-15 做梦的wls (20 分)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。