【题目描述】
礼品店一共有N件礼物排成一列,每件礼物都有它的美观度。排在第$i(1\leq i\leq N)$个位置的礼物美观度为正整数$A_I$。JYY决定选出其中连续的一段,即编号为礼物$i,i+1,…,j-1,j$的礼物。选出这些礼物的美观程度定义为:$(M(i,j)-m(i,j))/(j-i+K)$,其中$M(i,j)$表示$max{A_i,A_{i+1}\dots A_j}$,$m(i,j)$表示$min{A_i,A_{i+1}\dots A_j}$,$K$为给定的正整数。
由于不能显得太小气,所以JYY所选礼物的件数最少为$L$件;同时,选得太多也不好拿,因此礼物最多选$R$件。JYY应该如何选择,才能得到最大的美观程度?由于礼物实在太多挑花眼,JYY打算把这个问题交给会编程的你。
【输入格式】
本题每个测试点有多组数据。输入第一行包含一个正整数$T(T\leq 10)$,表示有T组数据。 每组数据包含两行,第一行四个非负整数$N,K,L,R(2\leq L\leq R\leq N)$。第二行包含$N$个正整数,依次表示$A_1,A_2….A_n$,$(A_i\leq 10^8)$,$N, K\leq 50,000$。
【输出格式】
输出$T$行,每行一个非负实数,依次对应每组数据的答案,数据保证答案不会超过$10^3$。输出四舍五入保留4位小数。

【思路】
这题暴力还是比较好写的,直接枚举礼物件数。。。良心题目
下面是正解:
很明显较优的一个区间取法是取一段区间$[l, r]$使得该区间最大值和最小值其中一个位于$A[l]$,另一个位于$A[r]$。因为如果使用这种取法,对于每对该区间内的最小值和最大值,$(r - l + k)$会尽量小。
所以分类讨论:
$1$区间大小小于限制$L$此时必须将区间大小扩大到$L$直接用单调队列维护长度为$L$区间的最大最小值,分别计算$n-L+1$个区间。
$2$二分答案$x$
对于一个区间$[L, R]$:
如果最大值在$A[L]$处,最小值在$A[R]$处,则有$A[L]-A[R]-(R-L+K) * x > 0$; 若$max((A[i]+i * mid)-(A[j]+j * mid)-k * mid)>=0$则$x$可以继续扩大。
如果最大值在$A[R]$处,最小值在$A[L]$处,则计算 $max((A[i]-i * mid)-(A[j]-j * mid)-k * mid)$是否大于0。
将$k * mid$移到不等式右边,剩下的$(A[i]-i * mid)$最大值可以用单调队列维护。
可以每次枚举位于左端点或右端点当作最大值,然后在合法的范围内通过单调队列找出一个最小值进行计算。
这题就做完了 好像依然没讲清楚
上代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87
| #include <bits/stdc++.h> #define ri register int using namespace std; typedef long long ll;
ll t, n, k, l, r; ll st1, st2, ed1, ed2; ll que1[50005], que2[50005]; ll q[50005], head, tail; ll a[50005]; double cur[50005]; double ans;
ll read() { ll ret = 0, flag = 1; char ch = getchar(); while (ch > '9' || ch < '0') { if (ch == '-') flag = -1; ch = getchar(); } while (ch <= '9' && ch >= '0') { ret = ret * 10 + ch - '0'; ch = getchar(); } return ret * flag; }
bool check(double mid) { for (ri i = 1; i <= n; i++) { cur[i] = a[i] - mid * i; } head = 1; tail = 0; double nowans = -1e9; for (ri i = l + 1; i <= n; i++) { while (head <= tail && i - q[head] >= r) head++; while (head <= tail && cur[q[tail]] >= cur[i - l]) tail--; q[++tail] = i - l; nowans = max(nowans, cur[i] - cur[q[head]]); } for (ri i = 1; i <= n; i++) { cur[i] = a[i] + mid * i; } head = 1; tail = 0; for (ri i = n - l; i >= 1; i--) { while (head <= tail && q[head] - i >= r) head++; while (head <= tail && cur[q[tail]] >= cur[i + l]) tail--; q[++tail] = i + l; nowans = max(nowans, cur[i] - cur[q[head]]); } return nowans >= k * mid; }
int main() { t = read(); while (t--) { n = read(); k = read(); l = read(); r = read(); for (ri i = 1; i <= n; i++) { a[i] = read(); } st1 = st2 = 1; ed1 = ed2 = 0; for (ri i = 1; i < l; i++) { while (st1 <= ed1 && a[que1[ed1]] >= a[i]) ed1--; while (st2 <= ed2 && a[que2[ed2]] <= a[i]) ed2--; que1[++ed1] = que2[++ed2] = i; } ans = -1e9; for (ri i = l; i <= n; i++) { while (st1 <= ed1 && i - que1[st1] >= l) st1++; while (st2 <= ed2 && i - que2[st2] >= l) st2++; while (st1 <= ed1 && a[que1[ed1]] >= a[i]) ed1--; while (st2 <= ed2 && a[que2[ed2]] <= a[i]) ed2--; que1[++ed1] = que2[++ed2] = i; ans = max(ans, 1.0 * (a[que2[st2]] - a[que1[st1]]) / (l + k - 1)); } double l = 0, r = 1005, mid; while (r - l >= 1e-7) { mid = (l + r) / 2; if (check(mid)) { l = mid + 0.000001; ans = max(ans, mid); } else r = mid - 0.000001; } printf("%.4lf\n", ans); } return 0; }
|