#C241123B. 连接处

标签（Label）

网址（Website）

题目详情 - 连接处 - Super

题解 - 连接处 - Super

题目（Problem）

题解（Solution）

出题者题解

代码（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-10
#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;

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

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

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

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

int l[N],p[N],w[N],d[N];
int n,x,y;

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

P st[N];int hd,tl;
bool check(int k){
	hd=0,tl=1;
	int l=0,r=0;
	For(i,1,n){
		while(l<=i && ask(w,l,i)>x)
	} 
}

void Solve(){
	n=rd(),x=rd(),y=rd();For(i,1,n) l[i]=rd();For(i,1,n) p[i]=rd();
	For(i,1,n) w[i] = w[i-1] + l[i]*p[i];
	For(i,1,n) d[i] = d[i-1] + l[i];
	
	double l=0,r=w[n],mid,res=-1;
	while(r-l>eps){
		mid = (l+r)/2;
		if(check(mid)) l=mid,res=mid;
		else r=mid;
	}printf("%.10Lf\n",res);
}

bool ED;
signed main(){
	cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
	freopen("connect1.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;
}