信息学奥赛一本通T1434：二分与三分 Best Cow Fences

【题目描述】给定一个长度为n的正整数序列A。求一个平均数最大的，长度不小于L的子序列。【输入】第一行，n和L；n个正整数，表示A。【输出】一个整数，表示答案的1000倍（不用四舍五入，直接输出）。【输入样例】10 6 【输出样例】6500【源程序】

信息学奥赛一本通T1434：Best Cow Fences

【题目描述】

给定一个长度为n的正整数序列A。求一个平均数最大的，长度不小于L的子序列。

【输入】

第一行，n和L；

n个正整数，表示A。

【输出】

一个整数，表示答案的1000倍（不用四舍五入，直接输出）。

【输入样例】

10 6
6 4 2 10 3 8 5 9 4 1

【输出样例】

6500

【源程序】

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#define PI acos(-1.0)
#define INF 0x3f3f3f3f
#define LL long long
#define Pair pair<int,int>
const double EPS = 1E6;
const int MOD = 1E9+7;
const int N = 1000000+5;
const int dx[] = {-1,1,0,0,-1,-1,1,1};
const int dy[] = {0,0,-1,1,-1,1,-1,1};
using namespace std;

int n,f;
double a[N];
double sub[N];
double sum[N];
int main() {
    scanf("%d%d",&n,&f);
    for(int i=1;i<=n;i++)
        scanf("%lf",&a[i]);

    double left=-1E6,right=1E6;
    while(right-left>1E-5){
        double mid=(left+right)/2.0;
        for(int i=1;i<=n;i++){
            sub[i]=a[i]-mid;//作差
            sum[i]=sum[i-1]+sub[i];//前缀和
        }

        double ans=-1E10;
        double minn=1E10;
        for(int i=f;i<=n;i++){
            minn=min(minn,sum[i-f]);
            ans=max(ans,sum[i]-minn);
        }

        if(ans>=0)
            left=mid;
        else
            right=mid;
    }
    printf("%d\n",right*1000);

    return 0;
}

信息学奥赛一本通T1434：二分与三分 Best Cow Fences 归属于二分与三分，更多同类题解源程序见：二分与三分和 Best Cow Fences

发表于 2020-05-20 10:20
阅读 ( 867 )
分类：信息学奥赛一本通

信息学奥赛一本通T1434：二分与三分 Best Cow Fences

信息学奥赛一本通T1434：Best Cow Fences

【题目描述】

【输入】

【输出】

【输入样例】

【输出样例】

【源程序】

你可能感兴趣的文章

相关问题

0 条评论

作家榜 »