心路历程
一开始没想到二分的check策略,看了题解才知道可以用单调队列维护一个区间长度为[S,T]的最大值,判断一下我们的区间值是否合法,合法则return true。
一些编码细节
- 二分的话因为我们枚举的是double型,所以用的是 - 比误差小的一个值作为单位长度(这题是1e-5),而如果是枚举int型的话,一般是减去单位长度 1 ;
- check的思路是先构造一个数组b[i],其第i位权值
b[i] = a[i] - d_li
(a[i]是原数组的第i位值,d_li是二分枚举的答案值) ,那么由于我们是求一个长度在[S,T
]的区间的最大平均值,那么这个区间一定满足这个区间的值的总和 - 区间长度 * 区间平均值 >= 0。因此对于每次二分,如果我们找到了一个区间满足 区间和 - 区间长度 * 区间平均值 >= 0 ,那就说明当前枚举的答案可选且如果求出来的是 > 0,说明答案还可以更大。 - 然后就是单调队列中的注意点,由于我们需要满足我们枚举的区间长度是位于 [S,T] 范围内的,所以我们是将
i - S
入队,然后队尾出队的条件就是( l <= r && sum[i] - sum[q[r]] < sum[i] - sum[q[l]] )
(如果[q[l],i]的区间和比[q[r],i]要大的话,那么就说明队尾还不如队头能得到的区间值大,那就丢掉队尾,一开始在想如果丢掉队尾后下一轮队头由于长度的问题也出去了,这样会不会漏了解,但是仔细想了想,既然队尾都出队了,就说明他够烂,与其用它还不如不把他那一位算在区间里面,而去选择后面的其他区间,因此这样算是不会漏解的),然后将sum[i]约一下就是( l <= r && sum[q[r]] > sum[q[l]] )
(这一步也可以这么去想,既然要求的是一个区间的最大值,而我们又是用前缀和作差求的区间,所以要结果值大,那在总值相等的情况下当然是希望我们要减去的值尽可能的小)
题目描述
给定一个长度为 $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 改编
时间复杂度 $O(nlog(2e4))$
C++代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define rep(a,b,c) for (int a = b ; a < c ; ++a)
using namespace std;
typedef long long ll ;
typedef pair<int,int> pii ;
const int maxn = 1e5 + 10 ;
char c,num[15];bool f;int len;
inline void R(int &x){
x = 0,f = 0,c = getchar();
while (c < '0' || c > '9' ){if (c == '-') f = 1;c = getchar();}
while (c >= '0'&& c <= '9' ){x = (x << 3) + (x << 1) + (c & 15) ; c = getchar() ;}
if (f) x = -x ;
}
inline void W(int x) {
if (!x) putchar('0');
len = 0;
if (x < 0) putchar('-'), x = -x;
while(x) num[++len] = (x % 10) + 48, x /= 10;
while(len) putchar(num[len--]);
}
int a[maxn],q[maxn],n,S,T;
double sum[maxn];
inline bool check(double d_li) {
for (int i = 1 ; i <= n ; ++i)
sum[i] = sum[i - 1] + a[i] - d_li ;
int l = 1,r = 0;
for (int i = S ; i <= n ; ++i){
while (l <= r && q[l] < i - T) ++l;
while (l <= r && sum[q[r]] > sum[i - S]) --r;
q[++r] = i - S ;
if (l <= r && sum[i] - sum[q[l]] >= 0) return true;
}
return false ;
}
int main(){
R(n),R(S),R(T);
for (int i = 1 ; i <= n ; ++i)
R(a[i]);
double l = -1e4,r = 1e4,mid;
while (r - l > 1e-5){
mid = (l + r) / 2;
if (check(mid)) l = mid ;
else r = mid - 1e-5;
}
printf("%.3f",l);
return 0;
}