洛谷1419 我的代码哪里有问题

Question

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

bool check(vector<int>& a, int n, int S, int T, double target){
    double sum = 0;
    double max_avg = 1e-9;
    queue<int> q;
    for(int i = 0; i < n; i++){
        sum += a[i];
        q.push(a[i]);
        
        if(q.size() > T){
            sum -= q.front();
            q.pop();
        }
        
        if(q.size() >= S){
            double avg = sum / q.size();
            max_avg = max(max_avg, avg);
        }
    }
    return max_avg >= target;
}

double binarySearch(vector<int>& a, int n, int S, int T){
    double left = 0;
    double right = 1e6;
    while(right - left >1e-6){
        double mid = left + (right - left)/2;
        if(check(a, n, S, T, mid)){
            left = mid;
        }
        else right = mid;
    }
    return left;
}
int main(){
    int n, S, T;
    cin >> n >> S >>T;
    vector<int> a(n);
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }
    double avg = binarySearch(a, n, S, T);
    printf("%.3lf\n", avg);
    return 0;
}

全红了

Answer 1

考虑的是每一段的平均价值。你的判断程序只有在队列长度超过最大限制时才会弹出元素，但是如果队头是一个很小的元素的话，可能更早把它弹出会更合理。所以你的这个思路是不行的。建议使用单调队列来求限定区间的最大值