开发笔记:poj1661

作者：森tu罗宝殿 | 来源：互联网 | 2023-10-13 09:21

HelpJimmy

Help Jimmy

Time Limit: 1000MS		Memory Limit: 10000K
Total Submissions:13756		Accepted: 4566

Description

"Help Jimmy" 是在下图所示的场景上完成的游戏。
技术分享图片

场景中包括多个长度和高度各不相同的平台。地面是最低的平台，高度为零，长度无限。
Jimmy老鼠在时刻0从高于所有平台的某处开始下落，它的下落速度始终为1米/秒。当Jimmy落到某个平台上时，游戏者选择让它向左还是向右跑，它跑动的速度也是1米/秒。当Jimmy跑到平台的边缘时，开始继续下落。Jimmy每次下落的高度不能超过MAX米，不然就会摔死，游戏也会结束。
设计一个程序，计算Jimmy到底地面时可能的最早时间。

Input

第一行是测试数据的组数t（0 <= t <= 20）。每组测试数据的第一行是四个整数N，X，Y，MAX，用空格分隔。N是平台的数目（不包括地面），X和Y是Jimmy开始下落的位置的横竖坐标，MAX是一次下落的最大高度。接下来的N行每行描述一个平台，包括三个整数，X1[i]，X2[i]和H[i]。H[i]表示平台的高度，X1[i]和X2[i]表示平台左右端点的横坐标。1 <= N <= 1000，-20000 <= X, X1[i], X2[i] <= 20000，0 Jimmy的大小和平台的厚度均忽略不计。如果Jimmy恰好落在某个平台的边缘，被视为落在平台上。所有的平台均不重叠或相连。测试数据保证问题一定有解。

Output

对输入的每组测试数据，输出一个整数，Jimmy到底地面时可能的最早时间。

Sample Input

1
3 8 17 20
0 10 8
0 10 13
4 14 3

Sample Output

Source

POJ Monthly--2004.05.15 CEOI 2000

AC代码

#include
#include
#include<iostream>
#include
#include
#include<string>
#include
#include
#define DEBUG(x) cout <<#x <<" = " <using namespace std;
const int MAXN=1e3+10;
const int INF=1<<30;
int N,X,Y,MAX;
struct Plat{
int x1,x2,h;
bool operator<(const struct Plat &p)const
{
return h>p.h;
}
};
Plat plats[MAXN];
int LeftMinTime[MAXN];
int RightMinTime[MAXN];
int main()
{
// freopen("in.txt","r",stdin);
int t;
scanf("%d",&t);
while(t--){
scanf("%d %d %d %d",&N,&X,&Y,&MAX);
for(int i=0;i){
scanf("%d %d %d",&plats[i].x1
,&plats[i].x2,&plats[i].h);
}
plats[N].x1=X,
plats[N].x2=X,
plats[N++].h=Y;
sort(plats,plats+N);
LeftMinTime[N-1]=plats[N-1].h,
RightMinTime[N-1]=plats[N-1].h;
for(int i=N-2;i>=0;i--){
bool f=false;
int j;
///LeftMinTime
for(j=i+1;j){
bool l=plats[i].x1>=plats[j].x1&&plats[i].x1<=plats[j].x2;
if(l){
f=l;
break;
}
}
if(f){
int d=plats[i].h-plats[j].h;
if(d<=MAX){
int l=abs(plats[i].x1-plats[j].x1)+LeftMinTime[j]+plats[i].h-plats[j].h;
int r=abs(plats[i].x1-plats[j].x2)+RightMinTime[j]+plats[i].h-plats[j].h;
LeftMinTime[i]=min(l,r);
}
else
LeftMinTime[i]=INF;
}
else {
if(plats[i].h>MAX){
LeftMinTime[i]=INF;
}
else {
LeftMinTime[i]=plats[i].h;
}
}
///RightMinTime
f=false;
for(j=i+1;j){
bool r=plats[i].x2>=plats[j].x1&&plats[i].x2<=plats[j].x2;
if(r){
f=r;
break;
}
}
if(f){
int d=plats[i].h-plats[j].h;
if(d<=MAX){
int l=abs(plats[i].x2-plats[j].x1)+LeftMinTime[j]+plats[i].h-plats[j].h;
int r=abs(plats[i].x2-plats[j].x2)+RightMinTime[j]+plats[i].h-plats[j].h;
RightMinTime[i]=min(l,r);
}
else{
RightMinTime[i]=INF;
}
}
else {
if(plats[i].h>MAX){
RightMinTime[i]=INF;
}
else{
RightMinTime[i]=plats[i].h;
}
}
}
printf("%d
",LeftMinTime[0]);
}
return 0;
}

推荐阅读

const
图论问题解析：POJ2762 从u到v或从v到u的可达性判断（强连通分量缩点与单向连通性检测）

本文深入探讨了POJ2762问题，旨在通过强连通分量缩点和单向连通性的判断方法，解决有向图中任意两点之间的可达性问题。文章详细介绍了算法原理、实现步骤，并附带完整的代码示例。 ... [详细]

蜡笔小新 2024-12-24 10:44:24
int
CUGB图论专题：排水系统中的最大流问题 - EK与Dinic算法解析

本题探讨如何通过最大流算法解决农场排水系统的设计问题。题目要求计算从水源点到汇合点的最大水流速率，使用经典的EK（Edmonds-Karp）和Dinic算法进行求解。 ... [详细]

蜡笔小新 2024-12-25 17:47:23
const
Codeforces Round #566 (Div. 2) A~F个人题解

Dashboard-CodeforcesRound#566(Div.2)-CodeforcesA.FillingShapes题意：给你一个的表格，你 ... [详细]

蜡笔小新 2024-12-25 18:41:21
const
毕业设计：基于机器学习与深度学习的垃圾邮件（短信）分类算法实现

本文详细介绍了如何使用机器学习和深度学习技术对垃圾邮件和短信进行分类。内容涵盖从数据集介绍、预处理、特征提取到模型训练与评估的完整流程，并提供了具体的代码示例和实验结果。 ... [详细]

蜡笔小新 2024-12-25 17:38:50
const
2016年10月25日数学考试：斐波那契数列与矩阵快速幂的应用

本次考试于2016年10月25日上午7:50至11:15举行，主要涉及数学专题，特别是斐波那契数列的性质及其在编程中的应用。本文将详细解析考试中的题目，并提供解题思路和代码实现。 ... [详细]

蜡笔小新 2024-12-25 13:08:21
const
2-SAT问题学习笔记

本文介绍了一种解决二元可满足性（2-SAT）问题的方法。通过具体实例，详细解释了如何构建模型、应用算法，并提供了编程实现的细节和优化建议。 ... [详细]

蜡笔小新 2024-12-24 21:48:43
java
Tetris 排名系统 (拓扑排序与并查集的应用)

本题旨在通过给定的评级信息，利用拓扑排序和并查集算法来确定全球 Tetris 高手排行榜。题目要求判断是否可以根据提供的信息生成一个明确的排名表，或者是否存在冲突或信息不足的情况。 ... [详细]

蜡笔小新 2024-12-24 21:03:51
int
GDI基础介绍之几何绘图

使用GDI的一些AIP函数我们可以轻易的绘制出简 ... [详细]

蜡笔小新 2024-12-25 18:23:37
const
深入理解线程局部存储

在多线程编程环境中，线程之间共享全局变量可能导致数据竞争和不一致性。为了解决这一问题，Linux提供了线程局部存储（TLS），使每个线程可以拥有独立的变量副本，确保线程间的数据隔离与安全。 ... [详细]

蜡笔小新 2024-12-25 17:04:36
const
实体映射最强工具类：MapStruct真香

实体映射最强工具类：MapStruct真香 ... [详细]

蜡笔小新 2024-12-25 16:22:17
int
多种方法实现求和序列 1+2+3+...+n

本文介绍了几种不同的编程方法来计算从1到n的自然数之和，包括循环、递归、面向对象以及模板元编程等技术。每种方法都有其特点和适用场景。 ... [详细]

蜡笔小新 2024-12-25 14:31:29
md5
Linux 透明防火墙（网桥模式）的部署与配置

本文介绍如何在现有网络中部署基于Linux系统的透明防火墙（网桥模式），以实现灵活的时间段控制、流量限制等功能。通过详细的步骤和配置说明，确保内部网络的安全性和稳定性。 ... [详细]

蜡笔小新 2024-12-25 13:17:38
int
私有成员属性的封装与访问控制

本文探讨了将类成员属性设置为私有的重要性，并通过具体代码示例展示了如何实现对这些属性的有效控制。私有成员属性有助于增强数据的安全性和完整性，确保只有经过验证的数据才能被修改。 ... [详细]

蜡笔小新 2024-12-25 11:53:51
client
优化局域网SSH连接延迟问题的解决方案

本文介绍了解决局域网内SSH连接到服务器时出现长时间等待问题的方法。通过调整配置和优化网络设置，可以显著缩短SSH连接的时间。 ... [详细]

蜡笔小新 2024-12-25 11:31:48
int
数据结构入门：栈的基本概念与操作

本文详细介绍了栈这一重要的数据结构，包括其基本概念、顺序存储结构、栈的基本操作（如入栈、出栈、清空栈和销毁栈），以及如何利用栈实现二进制到十进制的转换。通过具体代码示例，帮助读者更好地理解和应用栈的相关知识。 ... [详细]

蜡笔小新 2024-12-24 13:47:59

森tu罗宝殿

这个家伙很懒，什么也没留下！

Tags | 热门标签

RankList | 热门文章