显然二分答案,然后减去对应的mid,求超过L的最大子段和验证就好了。
当然记录下长度的直接DP也是可以的。
然而二分答案怎么都WA,很好奇为什么
直接输出r反而是能过的。
看了下https://blog.csdn.net/jiangshibiao/article/details/21963437
想起来double取整输出的时候要加上eps
1 /* *********************************************** 2 Author :BPM136 3 Created Time :2018/7/15 14:17:08 4 File Name :2018.cpp 5 ************************************************ */ 6 7 #include<iostream> 8 #include<cstdio> 9 #include<algorithm> 10 #include<cstdlib> 11 #include<cmath> 12 #include<cstring> 13 #include<vector> 14 using namespace std; 15 16 const int N = 100005; 17 const double eps = 1e-6; 18 19 double a[N]; 20 double b[N]; 21 double sum[N]; 22 int n,m; 23 24 int main() { 25 scanf("%d%d",&n,&m); 26 for(int i=1;i<=n;i++) scanf("%lf",&a[i]); 27 double l=-1e6,r=1e6; 28 while(r-l>eps) { 29 double mid=(l+r)/2; 30 for(int i=1;i<=n;i++) b[i]=a[i]-mid; 31 for(int i=1;i<=n;i++) sum[i]=sum[i-1]+b[i]; 32 double anss=-1e10; 33 double min_val=1e10; 34 for(int i=m;i<=n;i++) { 35 min_val=min(min_val,sum[i-m]); 36 anss=max(anss,sum[i]-min_val); 37 } 38 if(anss>=0) l=mid; else r=mid; 39 } 40 cout<<int((l+eps)*1000)<<endl; 41 return 0; 42 }