P12327 [蓝桥杯 2023 省 Java B] 蜗牛

题目描述

这天，一只蜗牛来到了二维坐标系的原点。

在 $x$ 轴上长有 $n$ 根竹竿。它们平行于 $y$ 轴，底部纵坐标为 $0$，横坐标分别为 $x_1,x_2,\dots ,x_n$。竹竿的高度均为无限高，宽度可忽略。蜗牛想要从原点走到第 $n$ 个竹竿的底部也就是坐标 $(x_n,0)$。它只能在 $x$ 轴上或者竹竿上爬行，在 $x$ 轴上爬行速度为 $1$ 单位每秒；由于受到引力影响，蜗牛在竹竿上向上和向下爬行的速度分别为 $0.7$ 单位每秒和 $1.3$ 单位每秒。

为了快速到达目的地，它施展了魔法，在第 $i$ 和 $i+1$ 根竹竿之间建立了传送门（$0<i<n$），如果蜗牛位于第 $i$ 根竹竿的高度为 $a_i$ 的位置 $(x_i,a_i)$，就可以瞬间到达第 $i+1$ 根竹竿的高度为 $b_{i+1}$ 的位置 $(x_{i+1},b_{i+1})$，请计算蜗牛最少需要多少秒才能到达目的地。

输入格式

输入共 $1+n$ 行，第一行为一个正整数 $n$；

第二行为 $n$ 个正整数 $x_1,x_2,\dots ,x_n$；

后面 $n-1$ 行，每行两个正整数 $a_i,b_{i+1}$。

输出格式

输出共一行，一个浮点数表示答案（四舍五入保留两位小数）。

输入输出样例 #1

输入 #1

3
1 10 11
1 1
2 1

输出 #1

4.20

说明/提示

样例说明

蜗牛路线：$(0,0)\to (1,0)\to (1,1)\to (10,1)\to (10,0)\to (11,0)$，花费时间为 $1+\frac{1}{0.7}+0+\frac{1}{1.3}+1\approx 4.20$

评测用例规模与约定

对于 $20\%$ 的数据，保证 $n\le 15$；

对于 $100\%$ 的数据，保证 $1\le n\le 10^5$，$1\le a_i,b_i\le 10^4$，$1\le x_i\le 10^9$。

C++实现

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,a[N],b[N],x[N];
double dp[N][2];//状态定义 
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",x+i);
	for(int i=1;i<n;i++) scanf("%d%d",a+i,b+i);
	memset(dp,0x3f,sizeof(dp)); 
	dp[0][0]=0;
	dp[1][0]=dp[1][1]=x[1];
	for(int i=2;i<=n;i++){//按照题目描述计算时间
		dp[i][0]=min(dp[i-1][1]+x[i]-x[i-1],dp[i-1][0]+x[i]-x[i-1]);
		double last=0;
		if(a[i-1]<b[i-2]) last=(b[i-2]-a[i-1])/1.3;
		else last=(a[i-1]-b[i-2])/0.7;
		dp[i][1]=min(dp[i-1][0]+a[i-1]/0.7+b[i-1]/1.3,dp[i-1][1]-b[i-2]/1.3+last+b[i-1]/1.3);
	}
	printf("%.2lf",min(dp[n][0],dp[n][1]));//输出答案 
	return 0; 
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容