#C241123B. 连接处

贪心 二分答案 推式子 双指针 单调队列优化
题目
发布日期:   2024-11-23
更新日期:   2024-11-29
文章字数:   2.4k
阅读时长:   12 分

#C241123B. 连接处

标签（Label）

  • 二分答案
  • 双指针
  • 推式子
  • 贪心
  • 单调队列优化

网址（Website）

题目详情 - 连接处 - Super

题解 - 连接处 - Super

题目（Problem）

输入数据 1

4 8 10
1 10 2 3
4 1 3 2

输出数据 1

2.6666666667

【样例1解释】

你可以选取 $2$ 单位长度密度是 $3$ 的，以及 $1$ 单位长度密度是 $2$ 的。

具体的，该钢管可看成 $[0,1)$ 密度是 $4$ , $[1,11)$ 密度是 $1$，$[11,13)$ 密度是 $3$，$[13,16)$ 密度是 $2$ 的结构。

那我选取的区间是 $[11,14)$ 质量为 $8$，长度为 $3$。

【样例2】

见选手目录下的 $connect/connect2.in$ 与 $connect/connect2.ans$。

【样例3】

见选手目录下的 $connect/connect3.in$ 与 $connect/connect3.ans$。

题解（Solution）

发现题目要求一个最大值，而且还是浮点数，很明显能发现答案有单调性，想到了二分答案。

考虑当前已经求出来了一个 $mid$ ，那么我们要怎么处理这个问题。

首先，我们会发现最后截出来的一段一定是一堆整的，外加一节部分段，很明显如果左右两边都选一定是不优的，我肯定会去选那个密度更大的一节。

其次，只有在凑质量 $L$ 或者在凑质量 $R$ 的时候我们才会截取一节而不用整的一段，不然要么不选要么选完。

现在考虑二分，由于出现区间，很容易想到前缀和，那么就处理出前缀质量和前缀长度 $w_i$ 和 $d_i$ ，那么我们就是要找到满足 $\frac{w_i-w_j}{d_i-d_j}\ge mid\mid j\le i$ 的区间，转化一下就是求 $j\le i$ 满足 $w_i-mid\times d_i\ge w_j-mid\times d_j$ 的存在性，那么对于一个 $i$ 我们就是要找到其向左的区间 $[l,r]$ 满足 $w_i-w_j\in[L,R]\mid j\in[l,r]$ ，并且在这个区间里面寻找到一个最小的 $w_j-mid\times d_j\mid j\in[l,r]$ ，这个东西可以使用单调队列 $O(n)$ 做。

除此之外，我们还要考虑截取部分段的贡献，考虑什么时候会截取部分段，很明显只有质量不够需要补全的时候或者部分段密度比平均密度高的时候我们才会让当前的整段在加入一个部分段。这里细讲一下为什么要补到 $R$ ，可能出现当前段最左边的区间密度大于要补充的部分段的情况，这种时候为了补充部分段而减少左区间一定是不优的，而我们只有在想将部分段全部放入但是发现放不下的时候才被迫选择截取，因此要补全到 $R$ 。

总结一下，固定一个区间作为段的左端点，并且延伸向右，如果出现选少于 $L$ 且答案更大的情况，我们至少要补全到 $L$ ，因此要截取一段部分段；如果出现在 $[L,R]$ 之间，我们直接取整段，如果加入新的段优的话就直接取，不优就整段都不要，这个使用上面的单调栈维护；只有想加入新的段却发现加入后总质量会超过 $R$ 时，我们才会考虑截取较优的一段。

由于每个区间作为段的左右端点都会枚举，因此一定能枚举到最优的左端点，并且匹配上最佳的符合答案的答案。

时间复杂度：$O(n\log \omega)$ ，$\log w$ 看实现时要二分多少次。

出题者题解

代码（Code）

35分
#include<bits/stdc++.h>
#include<vector>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
#define show(a) For(i,1,n) cerr<<a[i]<<' ';cerr<<'\n'
using namespace std;
#define P pair<int,int> 
#define int long long
#define double long double
#define x first
#define y second
inline int rd(){
	char c;bool f=false;while(!isdigit(c=getchar()))f=c=='-';int x=c^48;
	while(isdigit(c=getchar())){x=(((x<<2)+x)<<1)+(c^48);}return f?-x:x;
}template<typename G>
void write(G x){
	if(x<0) putchar('-'),write(-x);
	else if(x<=9) putchar('0'+x);
	else write(x/10),putchar('0'+x%10);
}constexpr int inf = 0x3f3f3f3f3f3f3f3f;
constexpr int N = 1012345;
bool ST;int Tt;

/*
n个材质，长度为li，单位质量为pi
选取总质量在[L,R]内的连续段，使单位质量最大 

两个要求：
1.质量在[L,R]内
2.密度最大 

双指针？可用于控制质量 --不可能，无法得知截断的位置 
dp？求最大 --不可能，因为可以从任何地方截断 
二分答案？ 假设已经知道了当前的单位质量 ，可以干什么？
判断是否存在一个区间使得总质量在[L,R]内且密度大于mid
如何判断？

最后裁出来的区间一定可以是包含了一个端点的形式，考虑枚举答案区间包含的左右端点，最后肯定是尽量向密度更大的区间去延伸，延伸可以直接计算
只枚举左端点如何计算右端点？ 由于质量的限制，二分找到[l,r]使w[i:l]=L, w[i:r]=R，注意判断边界：l,r<=n 
*/

int s[N],p[N],c[N],d[N];
int n,L,R;
double ans;

inline int ask(int *c,int l,int r){return c[r]-c[l];}
void Solve(){
	n=rd(),L=rd(),R=rd();For(i,1,n) s[i]=rd();For(i,1,n) p[i]=rd();
	For(i,1,n) c[i] = c[i-1] + s[i]*p[i];
	For(i,1,n) d[i] = d[i-1] + s[i];
	For(i,1,n) For(j,i,n-1){
		if(ask(c,i,j)>R || ask(c,i-1,j+1)<L) continue;
		double tmp=ask(c,i,j), len=ask(d,i,j), rou=len ? tmp/len : 0;
		
			
		if(min(p[i], p[j+1]) >= rou){
			if(ask(c,i-1,j+1) <= R){
				tmp = ask(c,i-1,j+1);
				len = ask(d,i-1,j+1);
				rou = tmp/len;
			}else if(p[i] > p[j+1]){
				if(ask(c,i-1,j) < R){
					tmp = ask(c,i-1,j);
					len = ask(d,i-1,j);
					
					len += (R-tmp)/p[j+1];
					tmp = R, rou=tmp/len;
				}else{
					len += (R-tmp)/p[i];
					tmp = R, rou=tmp/len;
				}
			}else{
				if(ask(c,i,j+1) < R){
					tmp = ask(c,i,j+1);
					len = ask(d,i,j+1);
					
					len += (R-tmp)/p[i];
					tmp = R, rou=tmp/len;
				}else{
					len += (R-tmp)/p[j+1];
					tmp = R, rou=tmp/len;
				}
			}
		}else if(max(p[i], p[j+1]) < rou){
			if(p[i] > p[j+1]){
				if(ask(c,i-1,j) < L){
					tmp = ask(c,i-1,j);
					len = ask(d,i-1,j);
					
					len += (L-tmp)/p[j+1];
					tmp = L, rou=tmp/len;
				}else if(tmp < L){
					len += (L-tmp)/p[i];
					tmp = L, rou=tmp/len;
				}
			}else{
				if(ask(c,i,j+1) < L){
					tmp = ask(c,i,j+1);
					len = ask(d,i,j+1);
					
					len += (L-tmp)/p[i];
					tmp = L, rou=tmp/len;
				}else if(tmp < L){
					len += (L-tmp)/p[j+1];
					tmp = L, rou=tmp/len;
				}
			}
		}else if(p[i] >= rou){
			if(ask(c,i-1,j) < R){
				tmp = ask(c,i-1,j);
				len = ask(d,i-1,j);
				if(tmp < L){
					len += (L-tmp)/p[j+1];
					tmp = L, rou=tmp/len;
				}
			}else{
				len += (R-tmp)/p[i];
				tmp = R, rou=tmp/len;
			}
		}else if(p[j+1] >= rou){
			if(ask(c,i,j+1) < R){
				tmp = ask(c,i,j+1);
				len = ask(d,i,j+1);
				if(tmp < L){
					len += (L-tmp)/p[i];
					tmp = L, rou=tmp/len;
				}
			}else{
				len += (R-tmp)/p[j+1];
				tmp = R, rou=tmp/len;
			}
		}
		if(rou > ans) ans = rou;
	}printf("%.10Lf\n",ans);
}

bool ED;
signed main(){
	cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
	freopen("connect.in","r",stdin);
	freopen("connect.out","w",stdout);
	Tt=1;double Tim=clock();
	while(Tt--) Solve();
	return cerr<<"TIME:"<<(clock()-Tim)/CLOCKS_PER_SEC,0;
}
100分
#include<bits/stdc++.h>
#include<vector>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
#define show(a) For(i,1,n) cerr<<a[i]<<' ';cerr<<'\n'
using namespace std;
#define double long double
#define int long long
#define x first
#define y second
#define eps 1e-8
#define P pair<int,int> 
inline int rd(){
	char c;bool f=false;while(!isdigit(c=getchar()))f=c=='-';int x=c^48;
	while(isdigit(c=getchar())){x=(((x<<2)+x)<<1)+(c^48);}return f?-x:x;
}template<typename G>
void write(G x){
	if(x<0) putchar('-'),write(-x);
	else if(x<=9) putchar('0'+x);
	else write(x/10),putchar('0'+x%10);
}constexpr int inf = 0x3f3f3f3f3f3f3f3f;
constexpr int N = 1012345;
bool ST;int Tt;

int s[N],p[N];
int n,L,R;

inline int ask(int *c,int l,int r){return c[r]-c[l];}

struct Wolf{
	int w[N],d[N],pp[N];
	int q[N],hd,tl;
	void init(){For(i,1,n) w[i]=w[i-1]+s[i]*p[i], d[i]=d[i-1]+s[i], pp[i]=p[i];}
	double calc(int i,double m){return (double)w[i]-m*(double)d[i];}
	bool check(double mid){
		int l=0,r=0;hd=1,tl=0;
		for(int i=1,j=1;i<=n;i++){
			while(j<i && w[i]-w[j]>L){
				while(hd<=tl && calc(j,mid)<=calc(q[tl],mid)) tl--;
				q[++tl]=j;
				j++;
			}
			while(hd<=tl && w[i]-w[q[hd]]>R) hd++;//把超过 R 的部分去掉 
			if(hd<=tl) if(calc(i,mid)>=calc(q[hd],mid)) return 1;
			
			while(w[i]-w[l]>L) l++;
			while(w[i]-w[r]>R) r++;
			if(l) if(1.L*L/(d[i]-d[l]+1.L*(L-(w[i]-w[l]))/pp[l])>=mid) return true;
			if(r) if(1.L*R/(d[i]-d[r]+1.L*(R-(w[i]-w[r]))/pp[r])>=mid) return true;
		}return false;
	}
}F1,F2;

bool check(double mid){return F1.check(mid)|F2.check(mid);}
void Solve(){
	n=rd(),L=rd(),R=rd();For(i,1,n) s[i]=rd();For(i,1,n) p[i]=rd();
	F1.init(); reverse(s+1,s+n+1),reverse(p+1,p+n+1); F2.init();
	double l=1,r=1e6,mid,res=-1;
	while(r-l>eps){
		mid = (l+r)/2.0;
		if(check(mid)) l=res=mid;
		else r=mid;
	}printf("%.10Lf\n",res);
}

bool ED;
signed main(){
	cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
	freopen("connect.in","r",stdin);
	freopen("connect.out","w",stdout);
	Tt=1;double Tim=clock();
	while(Tt--) Solve();
	return cerr<<"TIME:"<<(clock()-Tim)/CLOCKS_PER_SEC,0;
}
文章作者: WolfDeer
文章链接: https://wolfdeer62456.github.iohttps://wolfdeer62456.github.io/2024/11/23/C241123B-%E8%BF%9E%E6%8E%A5%E5%A4%84/
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 WolfDeer !
贪心 二分答案 推式子 双指针 单调队列优化
赏
  目录