Description

給出包含一個N個整數(shù)的數(shù)組A。找出一段長度至少為K的連續(xù)序列，最大化它的平均值。
請注意：一段子序列的平均值是子序列中所有數(shù)的和除以它的長度。

Input

第一行包含兩個整數(shù)N(1<=N<=300000)，K(1<=K<=N)。
?第二行包含N個整數(shù)，代表數(shù)組A，1<=ai<=10^6。

Output

一行一個實數(shù)，代表最大的平均值。允許在0.001以內(nèi)的絕對誤差。

Sample Input

輸入1：
4?1
1?2?3?4
輸入2：
4?2
2?4?3?4
輸入3：
6?3
7?1?2?1?3?6

Sample Output

輸出1：
4.000000
輸出2：
3.666666
輸出3：
3.333333

Data Constraint

對于30%的數(shù)據(jù)，N<=5000。
對于100%的數(shù)據(jù)，1<=N<=300000,?1<=K<=N,?1<=Ai<=1000000。

?

題解

• 先二分出來一個平均值，然后將序列里的所有數(shù)減去二分出來的數(shù)
• 然后求一遍前綴和直接判斷就好了

代碼

1 #include <cstdio> 2 #include <cstring> 3 #define N 300010 4 using namespace std; 5 int n,k; 6 double l,r,mid,a[N],b[N],eps=1e-5; 7 bool check(int x) 8 { 9 double p=0; 10 for (int i=k;i<=n;i++) 11 { 12 if (b[i]-p>=0) return 1; 13 if (b[i-k+1]<p) p=b[i-k+1]; 14 } 15 return 0; 16 } 17 int main() 18 { 19 freopen("average.in","r",stdin),freopen("average.out","w",stdout),scanf("%d%d",&n,&k); 20 for (int i=1;i<=n;i++) scanf("%lf",&a[i]),r+=a[i]; 21 while (r-l>eps) 22 { 23 double mid=(l+r)/2.0; b[0]=0; 24 for (int i=1;i<=n;i++) a[i]-=mid,b[i]=b[i-1]+a[i]; 25 if (check(mid)) l=mid; else r=mid; 26 for (int i=1;i<=n;i++) a[i]+=mid; 27 } 28 printf("%.5lf",l); 29 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/Comfortable/p/10358964.html

總結

以上是生活随笔為你收集整理的[贪心][前缀和] Jzoj P4256 平均数的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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