11250: 【原1250】BestSubsequence

题目

题目描述

author: yixi 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1250

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

Sample Output

yyong119's solution

#include <cstdio>
#define MAX_N 100010
using namespace std;

long long a[MAX_N], sum[MAX_N];
int N, F;

int main() {

    scanf("%d%d", &N, &F);
    for (int i = 1; i <= N; i++) {
        scanf("%lld", &(a[i]));
        sum[i] = sum[i - 1] + a[i];
    }
    double res = -1;
    for (int j = 0, i = 0; i + F <= N; i++) {
        if (i > j && ((sum[i] - sum[j]) * (i + F - j) < (sum[i + F] - sum[j]) * (i - j)))
            j = i;
        if (res * (i - j + F) < sum[i + F] - sum[j])
            res = (double)(sum[i + F] - sum[j]) / (i - j + F);
    }
    printf("%d\n", (int)(1000 * res));
    return 0;
}