题解：P6087 [JSOI2015] 送礼物
CommandSR
·
·
题解
题意
link
题解
考虑对最优区间 [l, r] 进行分讨。
- 若 L \leq r-l+1 \leq R，则可以直接作为答案。
- 若 r-l+1 < L，可以把它的长度补成 L。
- 若 r-l+1 > R，无法补救，不能作为答案。
对于情况一，考虑分数规划，二分答案 mid。
\frac{M(l,r)-m(l,r)}{r-l+K} \ge mid
M(l,r)-m(l,r) \ge mid \cdot (r-l+K)
令 a_r 为区间最大值，a_l 为区间最小值。
(a_r-mid\cdot r) - (a_l-mid\cdot l) \ge mid\cdot K
令 b_i = a_i-mid\cdot i，c_i = a_i+mid\cdot i，分别跑一遍单调队列即可。
对于情况二，直接跑单调队列，也要讨论 $a_l$ 为区间最小值，$a_r$ 为区间最大值，和 $a_r$ 为区间最小值，$a_l$ 为区间最大值的不同情况。
对于情况三，不会作为答案。
## Code
```cpp
// Problem: P6087
#include <bits/stdc++.h>
#define ll long long
#define db double
#define sz(x) (int)x.size()
#define F(i, a, b) for (int i = (a); i <= (b); ++i)
#define D(i, a, b) for (int i = (a); i >= (b); --i)
using namespace std;
namespace IO {
#define typ ll
inline typ rd() {
typ x = 0; bool f = 1; char ch = getchar();
while (ch < '0' || ch > '9') { if (ch == '-') f = 0; ch = getchar(); }
while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
return (f ? x : (-x));
}
inline void wr(typ x) {
if (x < 0) putchar('-'), x = -x;
if (x < 10) putchar(x+'0');
else wr(x / 10), putchar(x%10+'0');
}
}
using namespace IO;
const int N = 1e5 + 5;
const db eps = 1e-6;
int n, K, L, R, a[N], q[N], ff, ee;
db b[N], c[N];
db Sol1() {
db ans = 0;
ff = 1, ee = 0;
F(i, 1, n) {
while (ff <= ee && i - q[ff] + 1 > L) ++ff;
if (ff <= ee) ans = max(ans, 1.0 * (a[i] - a[q[ff]]) / (L + K - 1));
while (ff <= ee && a[q[ee]] >= a[i]) --ee;
q[++ee] = i;
}
ff = 1, ee = 0;
F(i, 1, n) {
while (ff <= ee && i - q[ff] + 1 > L) ++ff;
if (ff <= ee) ans = max(ans, 1.0 * (a[q[ff]] - a[i]) / (L + K - 1));
while (ff <= ee && a[q[ee]] <= a[i]) --ee;
q[++ee] = i;
}
return ans;
}
bool check(db x) {
F(i, 1, n) b[i] = a[i] - x * i;
ff = 1, ee = 0;
F(i, 1, n) {
while (ff <= ee && i - q[ff] + 1 > R) ++ff;
if (ff <= ee && b[i] - b[q[ff]] - K * x >= 0) return 1;
int j = i - L + 1;
if (j > 0) {
while (ff <= ee && b[q[ee]] >= b[j]) --ee;
q[++ee] = j;
}
}
F(i, 1, n) c[i] = a[i] + x * i;
ff = 1, ee = 0;
F(i, 1, n) {
while (ff <= ee && i - q[ff] + 1 > R) ++ff;
if (ff <= ee && c[q[ff]] - c[i] - K * x >= 0) return 1;
int j = i - L + 1;
if (j > 0) {
while (ff <= ee && c[q[ee]] <= c[j]) --ee;
q[++ee] = j;
}
}
return 0;
}
db Sol2() {
db l = 0, r = 1e4, mid;
while (l + eps < r) {
mid = (l + r) / 2;
if (check(mid)) l = mid;
else r = mid;
}
return l;
}
void GOGOGO() {
n = rd(), K = rd(), L = rd(), R = rd();
F(i, 1, n) a[i] = rd();
cout << fixed <<setprecision(4) << max(Sol1(), Sol2()) << '\n';
}
int main() {
int T = rd();
F(gogo, 1, T) GOGOGO();
return 0;
}
```