4.3 传送门

2023-11-05 19:44
文章标签 传送门 4.3

本文主要是介绍4.3 传送门,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

算法设计与分析 4.3 传送门

题目描述

  现在有 n 个传送门,你处在第一个传送门的位置,第 i 个传送门可以将你传送到第 i-a[i] 到第 i+a[i] 范围内的任意一个传送门,请问你最少需要几次操作,使得你可以传送到最后一个传送门的位置。
  保证题目一定有解。

输入格式

第一行为一个正整数 n( 1 <= n <= 104
第二行 n 个整数 a[i](0 <= a[i]<=1000)

输出格式

输出一个整数,表示最少操作次数。

样例输入

5
2 3 1 1 4

样例输出

2

参考代码

#include <stdio.h>
/*
* 判断当前i+a[i]是否可以到达n-1的位置,可以则结束;
* 否则寻找i+1到i+a[i]范围内的最大值(j+a[j]);
* 然后i跳到j
* 重复
* 时间O(n)
*/
int main()
{//FILE* s;//freopen_s(&s,"5.txt", "r", stdin);int n, count = 0;scanf("%d", &n);int a[10001];for (int i = 0; i < n; i++){scanf("%d", &a[i]);}int i = 0, len = a[0], max;while (i<n-1) {max = 0;len = i + a[i];if (len >= n - 1) {count++;break;}for (int j = i + 1; j <= len; j++) {if (j + a[j] > max) {max = j + a[j];i = j;}}count++;}printf("%d", count);
}

这篇关于4.3 传送门的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/352078

相关文章

cd swoole-4.3.2

宝塔安装swoole 新建文件夹 mkdir swoole 切入到文件夹中,进行下载安装包 wget http://pecl.php.net/get/swoole-4.3.2.tgz 解压 tar -zxvf swoole-4.3.2.tgz cd swoole-4.3.2 进行如下操作 phpize ./configure ./configure --with-php-config=

Java 4.3 - Redis

目录 Redis 基础 Redis 简介 缓存数据的处理流程是什么样的? 为什么要用 Redis?(为什么要使用缓存?) Redis 除了做缓存之外,还可以做什么? Redis 可以做消息队列吗? Redis 数据类型  Redis 常用的数据类型有哪些? String 的应用场景有哪些? String 还是 Hash 来存储对象? Redis 如何实现一个排行榜

4.3 python 编辑单元格

4.3.1 clear_contents()函数和clear()函数–清楚单元格的内容和格式 表达式.clear_contents() Range对象的clear_contects()函数用于清除单元格的内容,但不会清除单元格的格式设置 表达式.clear() Range对象的clear()用于清楚单元格的内容和格式设置。 # 清除指定单元格区域的内容和格式import xlwings

yaffs2移植到linux-4.3.2

1. 简介 任务:将yaffs2移植到可在目标板上运行的linux-4.3.2 目标板: MINI2440 交叉编译器: arm-linux-gcc version 4.3.2 2. 准备工作 下载yaffs2源码, https://yaffs.net/get-yaffs 3. 移植工作 3.1 解压yaffs2源码 $ tar -xzf yaffs2-b6a3ae5.tar.gz

25考研计算机组成原理复习·4.3程序的机器级代码表示

目录 高级语言与机器级代码之间的对应 常见的算术运算指令 常见的逻辑运算指令 AT&T格式 v.s. Intel格式 选择语句的机器级表示 无条件转移指令——jmp 条件转移指令——jxxx 示例:选择语句的机器级表示 循环语句的机器级表示 用条件转移指令实现循环 用loop指令实现循环 函数调用机器级表示 call、ret指令 如何访问栈帧? 访问栈帧数据:push

Android 4.3 WIN7 64位系统 开发环境搭建 android sdk+eclipse

1.8.0/ 一、下载   1. 下载安装SDK,百度搜索android sdk 即可,作者选择的版本是r22.3   2. 下载64位 eclpise,   下载地址 http://www.eclipse.org/downloads/   3. 下载安装64位JDK,作者直接百度:Win-x64-jdk-7u5 。     3.1 或者官网下载最新版     http

[4 使用C++11解决内存泄漏问题] 4.1 shared_ptr / 4.2 unique_ptr / 4.3 weak_ptr

智能指针是存储指向动态分配(堆内存)对象指针的类。 通用实现技术是使用引用计数。每使用它一次,引用计数加1,每析构一次,引用计数减1,减为0时,删除所指向的堆内存。 C++11提供三种智能指针,std::shared_ptr,std::unique_prt和std::weak_ptr。需引用头文件。 4.1 shared_ptr共享的智能指针 shared_ptr使用引用计数,每一个s

Celery 4.3.0 在task中执行多线程任务

测试Celery任务能否使用多线程 在开发的调试过程中,发现如果在django项目里面或者celery的task中使用协程gevent的话,使用monkey补丁的时候会报错。 那么尝试了很久,发现在celery中是可以执行多线程的,下面来演示一下执行的示例。 编写使用多线程的task import threadingfrom time import sleep,ctimedef smok

4.3、Django - URL之URL映射

1、为什么Django项目在urls.py 文件中去寻找所有URL映射? 答:因为,在settings.py 文件中进行了配置。主要是ROOT_URLCONF = 'douAPI.urls'(根URL配置 = douAPI下urls.py)。 2、在urls.py 文件中所有的映射,都应该放在urlpatterns 中 。例如,urls.py # from django.conf.urls im

Part 4.3 区间动态规划

[NOI1995] 石子合并 题目描述 在一个圆形操场的四周摆放 N N N 堆石子,现要将石子有次序地合并成一堆,规定每次只能选相邻的 2 2 2 堆合并成新的一堆,并将新的一堆的石子数,记为该次合并的得分。 试设计出一个算法,计算出将 N N N 堆石子合并成 1 1 1 堆的最小得分和最大得分。 输入格式 数据的第 1 1 1 行是正整数 N N N,表示有 N N