洛谷P1419-寻找段落-题解

寻找段落

题目描述

给定一个长度为 $n$ 的序列 $a$，定义 $a_i$ 为第 $i$ 个元素的价值。现在需要找出序列中最有价值的“段落”。段落的定义是长度在 $[S, T]$ 之间的连续序列。最有价值段落是指平均值最大的段落。

段落的平均值 等于 段落总价值 除以 段落长度。

输入格式

第一行一个整数 $n$，表示序列长度。

第二行两个整数 $S$ 和 $T$，表示段落长度的范围，在 $[S, T]$ 之间。

第三行到第 $n+2$ 行，每行一个整数表示每个元素的价值指数。

输出格式

一个实数，保留 $3$ 位小数，表示最优段落的平均值。

样例 #1

样例输入 #1

3
2 2
3
-1
2

样例输出 #1

1.000

提示

【数据范围】

对于 $30\%$ 的数据有 $n \le 1000$。

对于 $100\%$ 的数据有 $1 \le n \le 100000$，$1 \le S \le T \le n$，$-{10}^4 \le a_i \le {10}^4$。

【题目来源】

tinylic 改编

P1419 寻找段落 - 洛谷

思路

由题目可以得知，答案范围具有单调性，且题目涉及浮点数，易得这是一道浮点数二分答案题，因此，我们可以check每一个相同区间的和的最大值（长度相同了嘛，那区间和的关系就是平均值的关系了），若能找出大于mid的区间则说明还有更大的最优解，反之没有。

• 涉及到求区间和，我们想到使用前缀和。
• 涉及到求区间最大值，我们可以使用单调队列，ST表，线段树这些数据结构，而此题需要遍历找出第一个大于mid的元素，类似滑动窗口，所以，个人认为使用单调对象最合适

AC代码

C++代码

#include <iostream>
#include <deque>
#include <algorithm>
#include <iomanip>

using namespace std;

template<typename T>
T binary_search_answer(const T &left, const T &right,
                       const function<bool(const T &, const T &)> &isKeep,
                       const function<bool(const T &)> &check) {
    T l = left, r = right;
    while (isKeep(l, r)) {
        T mid = (l + r) / 2;
        if (check(mid))
            l = mid;
        else
            r = mid;
    }
    return l;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(); cout.tie();
    int n, s, t;
    cin >> n >> s >> t;
    double sum[n + 1];
    int arr[n + 1];
    sum[0] = arr[0] = 0;
    deque<int> q;
    for (int i = 1; i <= n; ++i) {
        cin >> arr[i];
        sum[i] = sum[i - 1] + double(arr[i]);
    }
    cout << fixed << setprecision(3)
         << binary_search_answer<double>
         (-1e4, 1e4,

          [](const double &l, const double &r){
             return l + 1e-4 < r;
          },

          [&](const double &x) {
             for (int i = 1; i <= n; ++i)
                 sum[i] = sum[i - 1] + double(arr[i]) - x;
             q.clear();
             for (int i = s; i <= n; ++i) {
                 while (not q.empty() and i - q.front() > t)
                     q.pop_front();
                 while (not q.empty() and sum[q.back()] > sum[i - s])
                     q.pop_back();
                 q.push_back(i - s);
                 if (not q.empty() and sum[i] - sum[q.front()] >= 0)
                     return true;
             }
             return false;
         });
    return 0;
}

AC截图

C with STL代码(其实还是C++)

#include <cstdio>
#include <deque>

using namespace std;
double sum[100005];
int arr[100005], n, s, t;
deque<int> q;

bool check(double x) {
    for (int i = 1; i <= n; ++i)
        sum[i] = sum[i - 1] + double(arr[i]) - x;
    q.clear();
    for (int i = s; i <= n; ++i) {
        while (not q.empty() and i - q.front() > t)
            q.pop_front();
        while (not q.empty() and sum[q.back()] > sum[i - s])
            q.pop_back();
        q.push_back(i - s);
        if (not q.empty() and sum[i] - sum[q.front()] >= 0)
            return true;
    }
    return false;
}

int main() {
    scanf("%d%d%d", &n, &s, &t);
    sum[0] = arr[0] = 0;
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &arr[i]);
        sum[i] = sum[i - 1] + double(arr[i]);
    }
    double l = 1e-4, r = 1e4;
    while (l + 1e-4 < r) {
        double mid = (l + r) / 2;
        if (check(mid))
            l = mid;
        else
            r = mid;
    }
    printf("%.3lf", l);
    return 0;
}

AC截图