Platforms Jumping(贪心,处理策略)

文章目录

  • 题目描述
    • 输入格式
    • 输出格式
    • 样例输入1
    • 样例输出1
    • 样例输入2
    • 样例输出2
    • 样例输入3
    • 样例输出3
    • 提交链接
    • 提示
  • 解析
  • 参考代码

题目描述

有一条宽度为 n n n 的河流。河的左岸是 0 0 0 单元格,右岸是 n + 1 n+1 n+1 单元格(更正式地说,这条河可以表示为一串从 0 0 0 n + 1 n+1 n+1 编号,一共 n + 2 n+2 n+2 单元格)。河上还有 m m m 个木制平台,其中 i i i 个平台的长度为 c i c_i ci (因此 i i i 个平台占用了河上 c i c_i ci 个连续的单元格)。可以保证平台长度之和不超过 n n n

您现在站在 0 0 0 处,并希望以某种方式到达 n + 1 n+1 n+1 。如果您站在位置 x x x 上,您可以跳到范围 [ x + 1 , x + d ] [x+1,x+d] [x+1,x+d] 中的任意位置。但是你并不喜欢水,所以你只能跳到属于某个木制平台的单元格。例如,如果是 d = 1 d=1 d=1 ,您只能跳到下一个位置(如果它属于木制平台)。您可以假设单元格 0 0 0 n + 1 n+1 n+1属于木质平台。

您想知道的是,如果您可以将任意平台向左或向右移动任意次数(可能是零),只要它们不相交(但两个平台可以相碰),那么是否有可能从 0 0 0 到达 n + 1 n+1 n+1 。这也意味着您不能改变平台的相对顺序。
注意,在开始跳跃之前,应先移动平台(换句话说,先移动平台,然后开始跳跃)。

例如,如果有 n = 7 n=7 n=7 m = 3 m=3 m=3 d = 2 d=2 d=2 c = [ 1 , 2 , 1 ] c=[1,2,1] c=[1,2,1] ,那么从 0 0 0 到达 8 8 8 的方法之一是遵循以下步骤:
在这里插入图片描述 n = 7 n=7 n=7

输入格式

输入的第一行包含三个整数 n 、 m n、m nm d ( 1 ≤ n , m , d ≤ 1000 , m ≤ n ) d(1 \leq n,m,d \leq 1000,m \leq n) d(1n,m,d1000,mn),分别是河流的宽度、平台的数量和跳跃的最大距离。

输入的第二行包含 m m m 个整数, c 1 , c 2 , . . . , c m ( 1 ≤ c i ≤ n , ∑ i = 1 m c i ≤ n ) c_1,c_2,...,c_m(1 \leq c_i \leq n,\sum\limits_{i=1}^{m}c_i \leq n) c1,c2,...,cm(1cin,i=1mcin),其中 c i c_i ci 是 第 i i i 个平台的长度。

输出格式

如果无法从 0 0 0 到达 n + 1 n+1 n+1 ,则在第一行打印 NO。否则,第一行打印 YES,第二行打印长度为 n n n 的数组 a a a - 河单元格序列(不包括单元格 0 0 0 和单元格 n + 1 n+1 n+1 )。

如果单元格 i i i 不属于任何平台,则 a i a_i ai 应为 0 0 0 。否则, a i a_i ai 应等于单元格 i i i 所属平台的索引( 平台按输入顺序从 1 1 1 m m m 编号)。

注意所有等于 1 1 1 a i a_i ai 应构成长度为 c 1 c_1 c1 的数组 a a a 的连续子块,所有等于 2 2 2 a i a_i ai 应构成长度为 c 2 c_2 c2 的数组 a a a 的连续子块,…,所有等于 m m m a i a_i ai 应构成长度为 c m c_m cm 的数组 a a a 的连续子块。 a a a 2 2 2 的最左端位置应大于 1 1 1 的最右端位置, a a a 3 3 3 的最左端位置应大于 2 2 2 的最右端位置,…, a a a m m m 的最左端位置应大于 m ? 1 m?1 m?1 的最右端位置。

样例输入1

7 3 2
1 2 1

样例输出1

YES
0 1 0 2 2 0 3 

样例输入2

10 1 11
1

样例输出2

YES
0 0 0 0 0 0 0 0 0 1 

样例输入3

10 1 5
2

样例输出3

YES
0 0 0 0 1 1 0 0 0 0 

提交链接

https://hydro.ac/d/lp728/p/15

提示

请看第一个例子:答案是 [ 0 , 1 , 0 , 2 , 2 , 0 , 3 ] [0,1,0,2,2,0,3] [0,1,0,2,2,0,3] 。你执行的跳跃序列是 0 → 2 → 4 → 5 → 7 → 8 0→2→4→5→7→8 024578

再看第二个例子:如何放置平台并不重要,因为你总是可以从 0 0 0 跳到 11 11 11

再看第三个例子:答案是 [ 0 , 0 , 0 , 0 , 1 , 1 , 0 , 0 , 0 , 0 ] [0,0,0,0,1,1,0,0,0,0] [0,0,0,0,1,1,0,0,0,0]。你的跳跃顺序是 0 → 5 → 6 → 11 0→5→6→11 05611

解析

此题的难点在于输出木板的位置。若单纯的判断是否能够到达,是比较简单的,直接每次跳跃最大距离。

现在每次跳跃最大距离可能导致木板没有办法放置。处理的办法,先把所有的木板按顺序放置再右边,同时记录编号。

n o w now now 记录当前的位置,若前面有木板,先走到木板的右边再开始跳,每次跳跃最大距离,落脚点若为水,则移动一个木板到当前的落脚点。

这样操作之后,能保证木板一定是在河流范围内且完美放下。

参考代码

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e3 + 9;
int n , m , d , c[maxn] , plat[maxn];
int main()
{
	cin >> n >> m >> d; //河流的宽度  平台的数量  跳跃的最大距离
	for(int i = 1; i <= m; i++)
		cin >> c[i];  //第i个平台的长度
	/*按顺序,先全部放在右边*/
	int x = n;
	for(int i = m; i >= 1; i--)
	{
		while(c[i])
		{
			plat[x--] = i;
			c[i]--;
		}
	} 
	int now = 0;
	while(1)
	{
		/*走到当前木板的最右边再开始跳,体现贪心*/
		while(now + 1 < n + 1 && plat[now + 1])
			now++;
		if(now + d >= n + 1)
			break;
		/*需要木板,找到最左边木板的左右端点*/
		 
		if(!plat[now + d])
		{
			int lpos = - 1 , rpos;
			for(int i = now + d; i <= n; i++)
			{
				if(plat[i])
				{
					lpos = i;
					break;
				}
			}
			if(lpos == -1)
			{
				cout << "NO";
				return 0;
			}
			for(int i = n; i > now + d; i--)
			{
				if(plat[i] == plat[lpos])
				{
					rpos = i;
					break;
				}
			}	
			while(!plat[now + d])
			{
				swap(plat[rpos] , plat[lpos - 1]);
				rpos--;
				lpos--;
			}
		}
		now += d;
	}
	cout << "YES" << endl;
	for(int i = 1; i <= n; i++)
		cout << plat[i] << " ";
	return 0;
}


本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/532590.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

MySQL基础练习题:习题2-3

这部分主要是为了帮助大家回忆回忆MySQL的基本语法&#xff0c;数据库来自于MySQL的官方简化版&#xff0c;题目也是网上非常流行的35题。这些基础习题基本可以涵盖面试中需要现场写SQL的问题。上期帮助大家建立数据库&#xff0c;导入数据&#xff0c;接下来让我们继续练习。 …

代码随想录35期Day08-字符串

344.反转字符串 位运算 func reverseString(s []byte) {l : 0r : len(s) - 1for l < r {s[l] ^ s[r]s[r] ^ s[l]s[l] ^ s[r]lr--} }541. 反转字符串II 没技巧 func reverseStringRange(s []byte, l int, r int) {if r > len(s) {r len(s) - 1}for l < r {s[l] ^…

c++的学习之路:22、多态(1)

摘要 本章主要是说一些多态的开头。 目录 摘要 一、多态的概念 二、多态的定义及实现 2.1、多态的构成条件 2.2、虚函数 2.3、虚函数的重写 2.4、C11 override 和 final 2.5、重载、覆盖(重写)、隐藏(重定义)的对比 三、思维导图 一、多态的概念 多态的概念&#…

Harmony鸿蒙南向驱动开发-Regulator

Regulator模块用于控制系统中各类设备的电压/电流供应。在嵌入式系统&#xff08;尤其是手机&#xff09;中&#xff0c;控制耗电量很重要&#xff0c;直接影响到电池的续航时间。所以&#xff0c;如果系统中某一个模块暂时不需要使用&#xff0c;就可以通过Regulator关闭其电源…

Vue3---基础2(component)

主要讲解 component 的创建 以及vue插件的安装 Vue.js Devtools 为谷歌浏览器的Vue插件&#xff0c;可以在调试工具内查看组件的数据等 下载 有两种下载方式 1. 谷歌应用商店 打开Chrome应用商店去下载&#xff0c;这个方法需要魔法 2. 极简插件 极简插件官网_Chrome插件下载_…

【图论】详解链式前向星存图法+遍历法

细说链式前向星存图法 首先要明白&#xff0c;链式前向星的原理是利用存边来进行模拟图。 推荐左神的视频–建图、链式前向星、拓扑排序 比方说有这样一张图&#xff0c;我们用链式前向星来进行模拟时&#xff0c;可以将每一条边都进行编号&#xff0c;其中&#xff0c;红色的…

SQL注入sqli_labs靶场第五、六题

第五题 根据报错信息&#xff0c;判断为单引号注入 没有发现回显点 方法&#xff1a;布尔盲注&#xff08;太耗时&#xff0c;不推荐使用&#xff09; 1&#xff09;猜解数据库名字&#xff1a;&#xff08;所有ASCII码值范围&#xff1a;0~127&#xff09; ?id1 and length…

数字化浪潮下,制造业如何乘势而上实现精益生产

随着数字化技术的迅猛发展&#xff0c;制造业正迎来前所未有的变革机遇。本文将探讨如何利用数字化手段助推制造业实现精益生产&#xff0c;从而在激烈的市场竞争中脱颖而出。 1、构建智能化生产系统 借助物联网技术&#xff0c;实现设备之间的互联互通&#xff0c;构建智能化…

【Qt踩坑】ARM 编译Qt5.14.2源码-QtWebEngine

1.下载源码 下载网站&#xff1a;Index of /new_archive/qt/5.14/5.14.2/single 2.QWebEngine相关依赖 sudo apt-get install flex libicu-dev libxslt-dev sudo apt-get install libssl-dev libxcursor-dev libxcomposite-dev libxdamage-dev libxrandr-dev sudo apt-get …

3. Spring 注解存储对象 Bean的命名规范

从Java5.0开始&#xff0c;Java开始支持注解。Spring做为Java生态中的领军框架&#xff0c;从2.5版本后也开始支持注解。相比起之前使用xml来配置Spring框架&#xff0c;使用注解提供了更多的控制Spring框架的方式。 SpringFramework版本对应jdk版本重要特性SpringFramework 1…

Linux——fork复制进程

1)shell: 在计算机科学中&#xff0c;Shell俗称壳&#xff08;用来区别于核&#xff09;&#xff0c;是指“为使用者提供操作界面”的软件&#xff08;command interpreter&#xff0c;命令解析器&#xff09;。它类似于DOS下的COMMAND.COM和后来的cmd.exe。它接收用户命令&…

练习题(2024/4/10)

1. 删除有序数组中的重复项 给你一个 非严格递增排列 的数组 nums &#xff0c;请你 原地 删除重复出现的元素&#xff0c;使每个元素 只出现一次 &#xff0c;返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。 考虑 nums 的唯一元…

安装VMware ESXi虚拟机系统

简介&#xff1a;ESXi是VMware公司开发的一款服务器虚拟化操作系统。它能够在一台物理服务器上运行多个虚拟机&#xff0c;每个虚拟机都可以独立运行操作系统和应用程序&#xff0c;而且对硬件配置要求低&#xff0c;系统运行稳定。 准备工具&#xff1a; 1.8G或者8G以上容…

查看TensorFlow已训模型的结构和网络参数

文章目录 概要流程 概要 通过以下实例&#xff0c;你将学会如何查看神经网络结构并打印出训练参数。 流程 准备一个简易的二分类数据集&#xff0c;并编写一个单层的神经网络 train_data np.array([[1, 2, 3, 4, 5], [7, 7, 2, 4, 10], [1, 9, 3, 6, 5], [6, 7, 8, 9, 10]]…

MySQL高级(索引结构Hash,为什么InnoDB存储引擎选择使用B+tree索引结构?)

目录 1、Hash索引结构 2、Hash索引特点 3、存储引擎支持 4、为什么InnoDB存储引擎选择使用Btree索引结构&#xff1f; 1、Hash索引结构 哈希索引就是采用一定的hash算法&#xff0c;将键值换算成新的hash值&#xff0c;映射到对应的槽位上&#xff0c;然后存储在hash表中。 如…

吴恩达机器学习-异常检测(Anomaly Detection)

在本练习中&#xff0c;您将实现异常检测算法&#xff0c;并将其应用于检测网络上出现故障的服务器。 文章目录 1-包2-异常检测2.1问题陈述2.2数据集2.3高斯分布2.2.1高斯实现的估计参数&#xff1a;2.2.2选择阈值&#x1d716; 2.4高维数据集 1-包 首先&#xff0c;让我们运…

脑电放大 LM386

LM386介绍 LM386 是一种音频集成功放&#xff0c;具有自身功耗低、电压增益可调整电源电压范围大、外接元件少和总谐波失真小等优点&#xff0c;广泛应用于录音机和收音机之中。 电源电压 4-12V 或 5-18V(LM386N-4);静态消耗电流为 4mA;电压增益为20-200dB;在引脚1和8开路时&a…

Android开发基础:事件传递 基于监听器的事件处理 基于回调的事件处理

目录 一&#xff0c;事件传递机制 1.事件传递机制的三个方法 &#xff08;1&#xff09;public boolean dispatchTouchEvent&#xff08;MotionEvent event&#xff09; &#xff08;2&#xff09;public boolean onInterceptTouchEvent&#xff08;MotionEvent event&…

【C++题解】1601. 挖胡萝卜

问题&#xff1a;1601. 挖胡萝卜 类型&#xff1a;基本运算、小数运算 题目描述&#xff1a; 小兔朱迪挖了 x 个胡萝卜&#xff0c;狐狸尼克挖到胡萝卜数量是小兔挖到的 3 倍&#xff0c;小羊肖恩挖到胡萝卜的数量比狐狸尼克少 8 个。 请你编程计算一下狐狸尼克和小羊肖恩分别…

时间系列预测总结

转载自&#xff1a;https://mp.weixin.qq.com/s/B1eh4IcHTnEdv2y0l4MCog 拥有一种可靠的方法来预测和预测未来事件一直是人类的愿望。在数字时代&#xff0c;我们拥有丰富的信息&#xff0c;尤其是时间序列数据。 时间序列是指基于时间刻度维度&#xff08;天、月、年等&…