首页 > 其他 > 详细

洛谷P1419寻找段落

时间:2019-05-19 16:56:23      阅读:34      评论:0      收藏:0      [点我收藏+]

标签:its   前缀和   show   i++   efi   pre   前缀   ont   www.   

题目

单调队列+前缀和

#include <bits/stdc++.h>
#define N 101001
using namespace std;
int n, s, t; int data[N];
double ans, temp[N], sum[N], l = -10000, r = 10000;
bool check(double a)
{
     deque <int> q;
    memset(sum, 0, sizeof(sum));
    for (int i = 1; i <= n; i++)
        temp[i] = (double) data[i] - a;
    sum[0] = 0;
    for (int i = 1; i <= n; i++)
        sum[i] = sum[i - 1] + temp[i];
    for (int i = 1; i <= n; i++)
    {                   
        if (i >= s) 
        {                   
            while (q.size() && sum[i - s] < sum[q.back()])
                q.pop_back();   
            q.push_back(i - s);
        }        
        if (q.size() && q.front() < i - t) 
        q.pop_front();
        if (q.size() && sum[i] >= sum[q.front()])    
            return true;
    }            
    return false;
}                
int main()       
{                
    scanf("%d%d%d", &n, &s, &t);
    for (int i = 1; i <= n; i++) scanf("%d", &data[i]);
    while (r - l > 0.00001)
    {            
        double mid = (l + r) / 2;
        if (check(mid))
        ans = l = mid;
        else     
        r = mid; 
    }
//  printf("%d", check(2));
    printf("%.3lf\n", ans);
    return 0;   
}               

洛谷P1419寻找段落

标签:its   前缀和   show   i++   efi   pre   前缀   ont   www.   

原文:https://www.cnblogs.com/liuwenyao/p/10889633.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 designnerd.net 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号