标签：格式   送礼物   set   输入输出   line   依次   log   01分数规划   整数   

P6087 [JSOI2015]送礼物 01分数规划+单调队列+ST表

题目背景

\(JYY\) 和 \(CX\) 的结婚纪念日即将到来，\(JYY\) 来到萌萌开的礼品店选购纪念礼物。

萌萌的礼品店很神奇，所有出售的礼物都按照特定的顺序都排成一列，而且相邻 的礼物之间有一种神秘的美感。于是，\(JYY\) 决定从中挑选连续的一些礼物，但究 竟选哪些呢？
题目描述

假设礼品店一共有 \(N\) 件礼物排成一列，每件礼物都有它的美观度。排在第 \(i\ (1\leqslant i\leqslant N)\) 个位置的礼物美观度为正整数 \(A_i\)?。\(JYY\) 决定选出其中连续的一段，即编号为 \(i,i+1,\cdots,j-1,j\) 的礼物。选出这些礼物的美观程度定义为

其中 \(M(i,j)\) 表示 \(\max\{A_i,A_{i+1},\cdots,A_j\}\)，\(m(i,j)\) 表示 \(\min\{A_i,A_{i+1},\cdots,A_j\}\)，\(K\) 为给定的正整数。 由于不能显得太小气，所以 \(JYY\) 所选礼物的件数最少为 \(L\) 件；同时，选得太多也不好拿，因此礼物最多选 \(R\) 件。\(JYY\) 应该如何选择，才能得到最大的美观程度？由于礼物实在太多挑花眼，\(JYY\) 打算把这个问题交给会编程的你。

输入格式

本题每个测试点有多组数据。

输入第一行包含一个正整数 \(T\)，表示有 \(T\) 组数据。

每组数据包含两行。第一行四个非负整数 \(N,K,L,R\)。第二行包含 \(N\) 个正整数，依次表示 \(A_1,A_2,\cdots,A_n\)?。

输出格式

输出 \(T\) 行，每行一个非负实数，依次对应每组数据的答案，数据保证答案不 会超过 \(10^3\)。输出四舍五入保留 \(4\) 位小数。

输入输出样例

输入

1
5 1 2 4
1 2 3 4 5

输出

0.7500

说明/提示

对于 \(100\%\) 的数据，\(T\leqslant 10,N,K\leqslant 5\times 10^4\)，\(1\leqslant A_i\leqslant 10^8\)，\(2\leqslant L,R\leqslant N\)。

分析

看到这一个式子，显然是 \(01\) 分数规划

但是一般的 \(01\) 分数规划都是上面一个求和公式比下面一个求和公式

而这一道题则是最大值减去最小值比区间长度加一个定值的形式

我们手玩一下会发现，一个区间的左右两端一定是该区间的最大值或最小值

因为如果你在最大值或者最小值的基础上继续扩展的话，分母会变大，结果会变小，肯定不利于我们求解

但是有可能最大值和最小值之间的元素个数小于最小的区间长度 \(l\) ，此时我们就必须向两边扩展

因此，我们分两种情况讨论：

\(1\) 、 区间的长度大于 \(l\)

此时，我们像正常的 \(01\) 分数规划一样二分枚举即可

我们设此时枚举到的价值为 \(mids\)

那么如果 \(\frac{M(i,j)-m(i,j)}{j-i+K} \geq mids\)

则有 \(\ M(i,j)-m(i,j) \geq mids \times (j-i+K)\)

根据之前推导的结论，两边的元素只能是最大值或者最小值

因此我们分类讨论

如果区间左边的元素大于区间右边的元素

则有 \(a[i]-a[j] \geq mids \times (j-i+K)\)

我们展开移一下项，就有

\(a[i]-a[j] \geq mids \times j- mids \times i +mids \times K\)

\(a[i]+i \times mids - a[j] - j \times mids \geq mids \times K\)

我们令 \(val[i]=a[i]+i \times mids\)

则就有 \(val[i]-val[j] \geq mids \times K\)

其中右边是一个常数

于是我们惊喜地发现这玩意可以用单调队列去搞一下

同理，如果区间左边的元素大于区间右边的元素

则有 \(a[j]-a[i] \geq mids \times (j-i+K)\)

\(a[j]-a[i] \geq mids \times j- mids \times i +mids \times K\)

\(a[j]- j \times mids - a[i] + i \times mids \geq mids \times K\)

我们令 \(val[i]=a[i]-i \times mids\)

则就有 \(val[j]-val[i] \geq mids \times K\)

也可以用单调队列去维护

\(2\) 、区间的长度等于 \(l\)

此时我们用 \(ST\) 表预处理出区间最大最小值

每次从左到右扫一边枚举左端点即可

代码

#include
using namespace std;
const int maxn=1e6+5;
const double eqs=1e-6;
int zdz[maxn][20],zxz[maxn][20],a[maxn],n,k,l,r;
double ans=0;
void solve1(){
	int cd=log2(l);
	for(int i=1;ir) headl++;
		if(headl=res) return 1;
		while(headlr) headr++;
		if(headr=res) return 1;
		while(headreqs){
		mmids=(ml+mr)/2;
		if(jud(mmids)) ml=mmids;
		else mr=mmids;
	}
	ans=max(ans,ml);
}//01分数规划
int main(){
	int t;
	scanf("%d",&t);
	while(t--){
		scanf("%d%d%d%d",&n,&k,&l,&r);
		ans=0;
		for(int i=1;i

P6087 [JSOI2015]送礼物 01分数规划+单调队列+ST表

标签：格式   送礼物   set   输入输出   line   依次   log   01分数规划   整数   

原文地址：https://www.cnblogs.com/liuchanglc/p/13485339.html