自动搬运

查看原文

来自洛谷，原作者为

	Laisira 初中数学考得跟小学数学一个逼分的废物

搬运于2025-08-24 23:06:08，当前版本为作者最后更新于2024-11-17 15:30:16，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

思路

连着两道小签题，梦熊真好心。

一个显然的暴力：

记 $f_{i,j}$ 表示到第 $i$ 个加油站的位置速度为 $j$ 的最小时间，有：

$$f_{i,j} = \min(f_{i-1,j}+\frac{p_{i}-p_{i-1}}{j},f_{i-1,\frac{j}{x_i}}+\frac{x_i(p_{i}-p_{i-1})}{j}+t_i) $$

然后在每个询问点上暴力取最小值，由于路程最大值（$y_{max}$）不超过 $10^9$，加油时间大于等于 $1$，所以速度不大于 $y_{max}$，乘的次数不大于 $\lceil\log y_{max}\rceil$，时间复杂度 $O(n\lceil\log y_{max}\rceil+nm)$。

不难发现瓶颈在统计答案，又 $x_{i}$ 只有四种情况（其中一种没用，一种可以被分解成 $2\times 2$），不妨记 $2$ 和 $3$ 分别被乘了几次，询问离线当成 $x_i = 1$ 去跑，时间复杂度 $O(n\lceil\log^2 y_{max}\rceil)$。

状态转移与上面大体一致。

UPDATE：少了个 $t_i$。

代码

#include<bits/stdc++.h>
#define int long long 
#define double long double 
#define m2 30
#define m3 25
using namespace std;
double f[2][m2][m3];
int fac[2][31];
struct node {
	int op,p,t,x;
	bool operator<(const node&is) {
		return p == is.p?op < is.op:p < is.p;
	}
} t[1000005];
double ans[100005];
double get(double x,double y) {
	return (double)x/y;
}
const double inf = 1e14;
const int INF = 1e13;
signed main()
{
//	freopen("ship4.in","r",stdin);
//	freopen("ship.out","w",stdout);
	int n,q,tot = 0;
	cin>>n>>q;
	for(int i=1;i<=n;i++) {
		int x,y,z;
		cin>>x>>y>>z;
		if(z == 1)continue;
		t[++tot] = {0,x,y,z};
	} 
	
	for(int i=1;i<=q;i++) {
		int x;
		cin>>x;
		t[++tot] = {i,x,0,1};
	} 
	
	sort(t+1,t+1+tot);
	
	for(int i=0;i<m2;i++)
		for(int j=0;j<m3;j++) {
			f[0][i][j] = inf;
			f[1][i][j] = inf;
		}
	f[0][0][0] = 0;
	
	fac[0][0] = fac[1][0] = 1;
	for(int i=1;i<m2;i++)
		fac[0][i] = fac[0][i-1]*2;
	for(int i=1;i<m3;i++)
		fac[1][i] = fac[1][i-1]*3;
	
	int res2 = 0,res3 = 0;
	
	for(int i=1;i<=tot;i++) {
		for(int j=0;j<=res2;j++) {
			for(int k=0;k<=res3;k++) {
				__int128 cnt = (__int128)fac[0][j]*fac[1][k]*t[i].x;
				if(cnt >= INF)break;
				f[(i&1)][j][k] = min(f[(i&1)][j][k],f[(i&1)^1][j][k]+get(t[i].p-t[i-1].p,fac[0][j]*fac[1][k]));
				if(t[i].x == 1)f[(i&1)][j][k] = f[(i&1)^1][j][k]+get(t[i].p-t[i-1].p,fac[0][j]*fac[1][k]);
				if(t[i].x == 2)f[(i&1)][j+1][k] = min(f[(i&1)^1][j+1][k]+get(t[i].p-t[i-1].p,fac[0][j+1]*fac[1][k]),f[(i&1)^1][j][k]+get(t[i].p-t[i-1].p,fac[0][j]*fac[1][k])+t[i].t);
				if(t[i].x == 3)f[(i&1)][j][k+1] = min(f[(i&1)^1][j][k+1]+get(t[i].p-t[i-1].p,fac[0][j]*fac[1][k+1]),f[(i&1)^1][j][k]+get(t[i].p-t[i-1].p,fac[0][j]*fac[1][k])+t[i].t);
				if(t[i].x == 4)f[(i&1)][j+2][k] = min(f[(i&1)^1][j+2][k]+get(t[i].p-t[i-1].p,fac[0][j+2]*fac[1][k]),f[(i&1)^1][j][k]+get(t[i].p-t[i-1].p,fac[0][j]*fac[1][k])+t[i].t);
			}
		}
		if(t[i].x == 2)res2 ++;
		if(t[i].x == 3)res3 ++;
		if(t[i].x == 4)res2 += 2;
		if(res2 > m2-1)res2 = m2-1;
		if(res3 > m3-1)res3 = m3-1;
		if(t[i].op) {
			double res = inf;
			for(int j=0;j<=res2;j++)
				for(int k=0;k<=res3;k++)
					res = min(res,f[(i&1)][j][k]);
			ans[t[i].op] = res;
		}
		for(int j=0;j<=res2;j++)
			for(int k=0;k<=res3;k++)
				f[(i&1)^1][j][k] = inf;
	} 
	for(int i=1;i<=q;i++)printf("%.7Lf\n",ans[i]);
	return 0;
 }