luogu P6087 [JSOI2015]送礼物二分单调队列决策单调性

LINK：送礼物

原本想了一个 \(nlog^2\)的做法然后由于线段树常数过大 T到30.

以为这道题卡\(log^2\)没想到真的有神仙写\(log^2\)的过了是我常数大了抱歉。

能过的\(log^2\)的做法是看到了一个决策单调性优化的dp 证明我不会。

不过由此得到的启示是一些类似或者就是dp的题目要多往决策单调性上想大胆猜想不管证明。

线段树的做法是二分之后也是维护dp的决策最优性。发现换set很难更换所以放弃治疗。

正解是一个log的做法：

考虑 M(i,j) 和 m(i,j) 之间的距离关系容易发现两种 i-j<=L-2 i-j>=L-1.

前者可以发现区间大小永远为L 后者可以发现i和j是区间的两端。

分类讨论对于第一种情况可以发现直接找到这样的l和r 然后由于区间大小固定所以直接计算即可。

考虑后者一个r可能存在很多的l 先二分一个mid.

可以得到 \(M(i,j)-m(i,j)-i\cdot mid+j\cdot mid>=k\cdot mid\)

考虑到最优解的l和r之间的距离是>=L-1的且分属两端那么强制认为 i为最大值 j为最小值对于每个i找到一个j即可。

这样的好处是可以发现一定可以扫到那个最优解且如果是j不是最小值或者i不是最大值那么刚才那个值只会更小不会更大.

至此两种情况讨论清楚了所以复杂度为nlogn.注意精度要高一点不然会wa.

//#include<bits\stdc++.h>

#include<iostream>

#include<iomanip>

#include<cstdio>

#include<cstring>

#include<string>

#include<ctime>

#include<cmath>

#include<cctype>

#include<cstdlib>

#include<queue>

#include<deque>

#include<stack>

#include<vector>

#include<algorithm>

#include<utility>

#include<bitset>

#include<set>

#include<map>

#define ll long long

#define db double

#define INF 1000000000

#define ldb long double

#define pb push_back

#define put_(x) printf("%d ",x);

#define get(x) x=read()

#define gt(x) scanf("%d",&x)

#define gi(x) scanf("%lf",&x)

#define put(x) printf("%d\n",x)

#define putl(x) printf("%lld\n",x)

#define gc(a) scanf("%s",a+1)

#define rep(p,n,i) for(RE int i=p;i<=n;++i)

#define go(x) for(int i=lin[x],tn=ver[i];i;tn=ver[i=nex[i]])

#define fep(n,p,i) for(RE int i=n;i>=p;--i)

#define pii pair<int,int>

#define mk make_pair

#define RE register

#define P 1000000007

#define F first

#define gf(x) scanf("%lf",&x)

#define pf(x) ((x)*(x))

#define ull unsigned long long

#define ui unsigned

#define EPS 1e-7

#define sq sqrt

#define mod 998244353

#define l(p) t[p].l

#define r(p) t[p].r

#define sum(p) t[p].sum

#define tag(p) t[p].tag

#define zz p<<1

#define yy p<<1|1

using namespace std;

char buf[1<<15],*fs,*ft;

inline char getc()

{

    return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;

}

inline int read()

{

    RE int x=0,f=1;RE char ch=getc();

    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getc();}

    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getc();}

    return x*f;

}

const int MAXN=50010;

int T,cnt,cnt1;

int n,k,L,R,maxx,l,r;

int a[MAXN],Log[MAXN];

int f[MAXN][20],q[MAXN];

inline int cmp(int x,int y){return a[x]>a[y]?x:y;}

inline int ask(int l,int r)

{

	int z=Log[r-l+1];

	return cmp(f[l][z],f[r-(1<<z)+1][z]);

}

inline int check(db mid)

{

	l=1;r=0;

	rep(L,n,i)

	{

		while(l<=r&&i-q[l]>=R)++l;

		while(l<=r&&(i-L+1)*mid-a[i-L+1]>=q[r]*mid-a[q[r]])--r;

		q[++r]=i-L+1;

		if(a[i]-i*mid-a[q[l]]+q[l]*mid>=k*mid)return 1;

	}

	l=1;r=0;

	rep(L,n,i)

	{

		while(l<=r&&i-q[l]>=R)++l;

		while(l<=r&&a[i-L+1]+(i-L+1)*mid>=a[q[r]]+q[r]*mid)--r;

		q[++r]=i-L+1;

		if(a[q[l]]+q[l]*mid-a[i]-i*mid>=k*mid)return 1;

	}

	return 0;

}

int main()

{

	freopen("1.in","r",stdin);

	get(T);

	rep(2,50000,i)Log[i]=Log[i>>1]+1;

	while(T--)

	{

		cnt=cnt1=maxx=0;

		get(n);get(k);get(L);get(R);

		rep(1,n,i)get(a[i]),f[i][0]=i;

		rep(1,Log[n],j)

			rep(1,n-(1<<j)+1,i)f[i][j]=cmp(f[i][j-1],f[i+(1<<(j-1))][j-1]);

		db ans=0;l=1;r=0;

		rep(1,n,i)

		{

			while(l<=r&&a[i]<=a[q[r]])--r;

			while(l<=r&&i-q[l]>=L-1)++l;

			q[++r]=i;

			if(i>=L-1)ans=max(ans,(a[ask(i-L+2,i)]-a[q[l]])*1.0/(L-1+k));

		}

		db wl=0,wr=1000;

		while(wl+EPS<wr)

		{

			db mid=(wl+wr)/2;

			if(check(mid))wl=mid;

			else wr=mid;

		}

		ans=max(ans,wl);

		printf("%.4lf\n",ans);

	}

	return 0;

}

巴特西

luogu P6087 [JSOI2015]送礼物二分单调队列决策单调性

最新文章

热门文章

巴特西

luogu P6087 [JSOI2015]送礼物 二分 单调队列 决策单调性

最新文章

热门文章

luogu P6087 [JSOI2015]送礼物二分单调队列决策单调性