tle球条!!
查看原帖
tle球条!!
925491
pengze36楼主2024/11/22 20:11
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<map>
#define re register 
#define ll long long 
using namespace std;
int n,q;
double p[100005],t[100005],x[100005];
map<int,int> ma,to;
int tot;
double f[100005][310];
int  sum=0;
int main(){
//	freopen("ship4.in","r",stdin);
	//freopen("ship4.outm","w",stdout);
	for(int i=1;i<=1e9;i*=2){
		for(int j=i;j<=1e9;j*=3){
			if(ma.find(j)==ma.end()){
			//	cout<<j<<endl;
				ma[j]=++tot;
				to[tot]=j;
			//	cout<<j<<endl;
			}
			if((ll)j*(ll)3>1e9) break;
		}
		if((ll)i*(ll)2>1e9) break;
	}
//	puts("//");
//	cout<<tot<<endl;
//	cout<<tot<<endl;
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;++i){
		++sum;
		scanf("%lf%lf%lf",&p[sum],&t[sum],&x[sum]);
		if(x[sum]==(double)1) sum--;
	}
	n=sum;
//	cout<<sum<<endl;
	p[0]=0;	
  for(int i=0;i<=n;++i){
  		for(int j=1;j<=tot;++j){
		f[i][j]=1e10;
	}
  }
	f[0][ma[1]]=0;
	//	cout<<"//";
//cout<<"//";
//cout<<n*tot<<endl;
	for(re int i=1;i<=n;++i){
		for(re int j=1;j<=tot;++j){
			int toj=to[j];
			f[i][j]=min(f[i][j],f[i-1][j]+(p[i]-p[i-1])/toj);
			if(f[i-1][j]!=1e10&&to[j]*x[i]<1e9){
			int y=ma[to[j]*x[i]];
			f[i][y]=min(f[i][y],f[i-1][j]+t[i]+(p[i]-p[i-1])/toj);
			}
		//	f[i][j]=1e10;
//	f[i][j]=min(f[(i-1)][j]+(p[i]-p[i-1])/to[j],(((int)to[j]%(int)x[i])==0)?(f[(i-1)][ma[(int)(to[j]/x[i])]]+t[i]+(p[i]-p[i-1])*x[i]/to[j]):1e10);
//	cout<<i<<" "<<j<<" "<<to[j]<<" "<<x[i]<<" "<<" "<<(((int)to[j]%(int)x[i])==0)<<" "<<f[(i-1)][ma[to[j]/x[i]]]<<" "<<p[i]<<" "<<p[i-1]<<" "<<to[j]<<" ";
//	printf("%.7lf\n",f[i][j]);
		}
	}

	
//	cout<<f[4][ma[12]]<<endl; 
	while(q--){
		int y;
		scanf("%d",&y);
		int i=lower_bound(p+1,p+1+n,y)-p;
		if(i>n) i=n+1;
		double ans=1e10;
			for(int j=1;j<=tot;++j){
        //double tmp=min(f[(i-1)][j]+(y-p[i-1])/to[j],(((int)to[j]%(int)x[i])==0)?(f[(i-1)][ma[to[j]/x[i]]]+(y-p[i-1])*x[i]/to[j]):1e10);
        //cout<<i<<" "<<f[(i-1)][j]<<" "<<(y-p[i-1])/to[j]<<" "<<f[(i-1)][ma[to[j]/x[i]]]+t[i]+(y-p[i-1])*x[i]/to[j]<<endl;
        ans=min(ans,f[(i-1)][j]+(y-p[i-1])/to[j]);
     //   if((f[(i-1)][j]+(y-p[i-1])/to[j])<300)cout<<to[j]<<" "<<f[(i-1)][j]+(y-p[i-1])/to[j]<<endl;
		}
		printf("%.7lf\n",ans);
	}
	
	return 0;
} 
2024/11/22 20:11
加载中...