「JSOI 2015」送礼物 （RMQ + 01分数规划）

题目摘要：

在一列礼物(v[1]，v[2] …… v[n])中选择长度满足要求(L<=长度<=R)的一段连续区间中的礼物，使得这一段中礼物美观度的最大值与最小值之差，与长度的比值最大，求出这个最大的比值。

题目分析：

先用01分数规划，可以设[M(i,j)-m(i,j)]/(j-i+k)<=ans，整理得[M(i,j)-m(i,j)]-ans*(j-i+k)<=0，然后对ans做二分即可，重点是二分中的check()函数怎么写：

如果题目没有限制选出礼物的长度，为了使比值最大，选出的这一段中美观度最大与最小的礼物一定位于区间的两端。而由于题目限制了区间的长度，因此我们应当分两种情况考虑：

1：区间的长度恰好为L，此时的判定条件即为：[M(i,j)-m(i,j)]-ans*(l-1+k)<=0，预处理出整个礼物序列的st表，再O(n)枚举起始点，逐个判定即可。

2：区间的长度大于L，此时仍分两种情况讨论，即左端点为最大值或最小值的两种不同情况。分别求出(v[i]-i*mid)-(v[j]-j*mid)与(v[i]+i*mid)-(v[j]+j*mid)的最大值之后与零进行比较即可。

代码：

#include<iostream>
using namespace std;
const double eps=1e-7;
int T;
int m,n,L,R;
int pq1[51015],l1,r1;
int pq2[51015],l2,r2;
int pq3[51015],l3,r3;
int a[51015];
double b[51015];
int main(){
	scanf("%d",&T);
	while(T--){
		scanf("%d%d%d%d",&m,&n,&L,&R);
		for(int i=1;i<=m;i++){
			scanf("%d",&a[i]);
		}
		l1=r1=l2=r2=0;
		for(int i=1;i<L;i++){
			while(l1<r1&&a[pq1[r1-1]]>=a[i]){
				r1--;
			}
			while(l2<r2&&a[pq2[r2-1]]<=a[i]){
				r2--;
			}
			pq1[r1++]=pq2[r2++]=i;
		}
		double ans1=-1000;
		for(int i=L;i<=m;i++){
			while(l1<r1&&i-pq1[l1]>=L){
				l1++;
			}
			while(l2<r2&&i-pq2[l2]>=L){
				l2++;
			}
			while(l1<r1&&a[pq1[r1-1]]>=a[i]){
				r1--;
			}
			while(l2<r2&&a[pq2[r2-1]]<=a[i]){
				r2--;
			}
			pq1[r1++]=pq2[r2++]=i;
			ans1=max(ans1,1.0*(a[pq2[l2]]-a[pq1[l1]])/(L-1+n));
		}
		double l=0,r=1000;
		while(r-l>eps){
			double mid=(l+r)/2;
			double cnt=-100000;
			l3=r3=0;
			for(int i=1;i<=m;i++){
				b[i]=a[i]-i*mid;
			}
			for(int i=L+1;i<=m;i++){
				while(l3<r3&&i-pq3[l3]>=R){
					l3++;
				}
				while(l3<r3&&b[pq3[r3-1]]>=b[i-L]){
					r3--;
				}
				pq3[r3++]=i-L;
				cnt=max(cnt,b[i]-b[pq3[l3]]);
			}
			l3=r3=0;
			for(int i=1;i<=m;i++){
				b[i]=a[i]+i*mid;
			}
			for(int i=m-L;i;i--){
				while(l3<r3&&pq3[l3]-i>=R){
					l3++;
				}
				while(l3<r3&&b[pq3[r3-1]]>=b[i+L]){
					r3--;
				}
				pq3[r3++]=i+L;
				cnt=max(cnt,b[i]-b[pq3[l3]]);
			}
			if(cnt>=mid*n){
				l=mid;
			}else{
				r=mid;
			}
		}
		printf("%.4f\n",max(ans1,l));
	}
	return 0;
}

「JSOI 2015」送礼物 （RMQ + 01分数规划）

原文：https://www.cnblogs.com/051011zzf/p/11273357.html