NOIP模拟 最佳序列 - 二分 + 单调队列

题意:

各一个n(\(\le 20000\))的序列,定义纯洁序列为长度len满足\(L \le len \le R\)的序列,纯洁值为某一纯洁序列的平局值,输出所有纯洁序列中最大平均值。

分析:

二分 + 单调队列:二分出平均值mid, 下面来判断该平均值是否符合加大L的要求:

\[mid = \frac{sum[i] - sum[p]}{i-p} (i - r + 1 <= p <= i - l + 1)
\]

当mid偏小时:\(\sum{(a_i - mid)} >= \sum{(a_j - mid)} (i - r + 1 <= j <= i - l + 1)\)

若\(min\{ \sum(a_j - mid) (i - r + 1 <= j <= i - l + 1)\} <= \sum{a_i - mid}\)那么就肯定满足了。

即要求指定区间中的最小值,直接单调队列。\(O(nlogn)\)

code:

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<ctime>
#include<deque>
using namespace std;
namespace IO {
template<typename T>
inline void read(T &x) {
T i = 0, f = 1;
char ch = getchar();
for(; (ch < '0' || ch > '9') && ch != '-'; ch = getchar());
if(ch == '-') f = -1, ch = getchar();
for(; ch >= '0' && ch <= '9'; ch = getchar()) i = (i << 3) + (i << 1) + (ch - '0');
x = i * f;
}
template<typename T>
inline void wr(T x) {
if(x < 0) putchar('-'), x = -x;
if(x > 9) wr(x / 10);
putchar(x % 10 + '0');
}
}using namespace IO; const int N = 2e4 + 5;
#define eps 1e-8
int n, l, r, a[N];
typedef long long ll;
double sum[N], ans;
deque<double> que; inline bool calc(double mid){
sum[0] = 0;
for(int i = 1; i <= n; i++) sum[i] = sum[i - 1] + 1.0 * a[i] - mid;
que.clear(); for(int i = l; i <= n; i++){
while(!que.empty() && sum[(int)que.back()] >= sum[i - l]) que.pop_back();
que.push_back(i - l);
while(!que.empty() && i - que.front() > r) que.pop_front();
if(!que.empty() && sum[i] >= sum[(int)que.front()]) return true;
}
return false;
} int main(){
freopen("h.in", "r", stdin);
read(n), read(l), read(r);
for(int i = 1; i <= n; i++) read(a[i]);
double L = 0, R = 1e6;
for(int t = 1; t <= 50; t++){
double mid = (L + R) / 2;
if(calc(mid)) L = mid;
else R = mid;
}
printf("%.4f", L);
return 0;
}
上一篇:安卓程序代写 网上程序代写[原]ViewGroup(容器组件)详解(API解析)


下一篇:[USACO12MAR]花盆 二分 单调队列