---恢复内容开始---

1250. BestSubsequence

Description

LL有n个妹子，他给妹子们编号排成一排。据说今天天气大好，LL要去春游了，他决定要选定至少F个妹子一起去玩。 为了让妹子们开心，他决定选连续一段的妹子们。然后LL有个特殊的癖好，他喜欢体重比较厉害一些的妹子。

那你可以帮LL选妹子吗，使得选出来的这些妹子的平均体重最大。

Input Format

输入第一行两个整数，n和F。

接下来n行，每行一个整数，表示妹子的体重。

对前50%的数据：1<=n<=20。 对100%的数据：1<=n<=100000, 1<=F<=n, 1<=妹子体重<=2000。

Output Format

输出一个整数，为这个平均值乘以1000，不要四舍五入，输出int(avergae * 1000)即可。

Sample Input

10 66 4210385941

Sample Output

6500 题目大意： 给出一个序列，长度为N，均为正数。 找出一段连续的区间，此区间的平均值最大，长度必须大于等于F。 1.二分答案法 O(nlgM)

首先留意到答案的输出是整数。想到答案的范围是可以根据输入确定的，而且范围较小（M<=2000） 所以可以用二分答案法 先猜测一个平均数A，来判断是否存在一个长度大于等于F的连续序列可以满足平均值大于A。 判断的方法可以利用一个成型的DP方法来解决这个问题，那就是寻找一个序列是否存在一个长度大于等于F的子序列和为正（每个数减去平均值即可）。 dp的状态转移方程就是: f[a, b] 表示在区间 [a, b] 中，所有子区间的最大值,最后只要判断 Then 当 b - a = F 时，f[a, b] 为序列中对应的和。 当 b - a > F 时，f[a, b] = max{ f[a, b - 1] + arr[b], f[b - f + 1, b] } 注意第二种情况下，如果遇到了以b结尾的连续F个元素的子序列的和更大一些，那就从此开始重新累加计算。 而且注意，二分法的时候一定要用double来二分 输出R while(L-R>1e-7) R=mod L=mod 都是关键点 代码如下:

#include 
       
        #include 
        
         using namespace std;const int MaxN = 100000+10;int n,F;int weight[MaxN];int preSum[MaxN];int Min;int Max;void Init(){    cin>>n>>F;    cin>>weight[1];    preSum[0] = 0;    Min = Max = preSum[1] = weight[1];    for (int i = 2; i <= n; ++i)    {        scanf("%d",&weight[i]);        preSum[i] = preSum[i-1] + weight[i];        Max = Max > weight[i] ? Max : weight[i];        Min = Min < weight[i] ? Min : weight[i];    }    return;}//因为Guess是由猜测确定的 它可能是F个 也可能是>F个数的avg 所以还是要考虑所有的情况inline bool BinarySearch(double guess){     double pre = 0.0;    double cur = 0.0;    //pre初始为前n-1项的 去掉guess的和    //pre 其实就是用来检查是否大于0的连续的那段    pre = (preSum[F-1] - preSum[0]) - guess * (F-1);    //从第F项开始遍历    for (int i = F; i <= n ; ++i)    {        //cur是某F项的 减去guess的和         cur = preSum[i] - preSum[i-F] - guess * F;        //pre 第一次循环是前F项的和        pre += weight[i] - guess;        //核心思想就是 如果整个pre还不如后F个大 那就要后F个即可        if(cur > pre)            pre = cur;        if(pre > -1e-6)            return true;    }    return false;}int main(int argc, char const *argv[]){    Init();    //注意因为真正二分的答案是去分析那个double的平均值 所以还是尽量用double 否则可能会出现刻度不够精细导致的错误    double L = Min;    double R = Max;    while(R - L >= 1e-6){        double mid = (L+R)/2;        //double类型的二分法         if(BinarySearch(mid)){ //说明这个猜测比较小            L = mid;        }else{            R = mid;        }    }    //注意这里必须输出R    cout<
         
          <
         
        
       

 

　　2.动态规划法 O(n)

核心的思想就是

先取前F-1个元素

分别维护i和j，认为 [j,i+F]就是答案

核心的思想很简单 就是如果j到i这一段的平均值小于i,到i+F这一段的平均值 则不要前半段了.

#include 
       
        #include 
        
         using namespace std;const int MaxN = 100000+10;//求最大平均的连续子列合 (至少连续F个元素) 考虑动态规划int weight[MaxN]={
     0};//表示每个妹子的体重int preSum[MaxN];//前缀和int main(int argc, char const *argv[]){    int n,F;    cin>>n>>F;    preSum[0] = 0;    for (int i = 1; i <= n; ++i){        scanf("%d",&weight[i]);        preSum[i] = preSum[i-1] + weight[i];    }    int ans = -1;    //最后toCheck的部分是 j 到 i+F 的这段     //核心思想就是 如果j到i这段是拉低了整个toCheck的部分 不如就不要了    //上面这一个核心思想非常像二分答案里 判断是否存在大于等于F项连续和大于0的思想      for (int i = 0, j = 0; i <= n - F; i++)    {        if (i > j && (preSum[i] - preSum[j]) * (i + F - j) < (preSum[i + F] - preSum[j]) * (i - j))            j = i;//如果i和j之间的子段平均值小于i到i+f之间的平均值，则将舍弃i和j之间的子段        if (ans < 1000 * (preSum[i + F] - preSum[j]) / (i + F - j))            ans = 1000 * (preSum[i + F] - preSum[j]) / (i + F - j);    }    cout<
         
          <