【万题详解】洛谷P1252 马拉松接力赛

2024-01-21 10:12

本文主要是介绍【万题详解】洛谷P1252 马拉松接力赛,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

前言

因为博主已经考完期末考试了,所以一定会多多更新。

P1252 马拉松接力赛

某城市冬季举办环城 25km马拉松接力赛,每个代表队有 5人参加比赛,比赛要求每个的每名参赛选手只能跑一次,一次至少跑 1km 、最多只能跑 10km,而且每个选手所跑的公里数必须为整数,即接力的地方在整公里处。

刘老师作为学校代表队的教练,精心选择了 5 名长跑能手,进行了训练和测试,得到了这 55 名选手尽力连续跑 1km、2km、…、10km 的所用时间。现在他要进行一个合理的安排,让每个选手跑合适的公里数,使学校代表队跑完 25km 所用的时间最短。根据队员的情况,这个最短的时间是惟一的,但安排方案可能并不惟一。

根据测试情况及一般运动员的情况得知,连续跑 1km 要比连续跑2km 速度快,连续跑 2km 又要比连续跑 3km 速度快……也就是说连续跑的路程越长,速度越慢,当然也有特殊的,就是速度不会变慢,但是绝不可能变快。

输入格式

5行数据,分别是 1 到 5号队员的测试数据,每行的 10个整数,表示某一个运动员尽力连续跑 1km 、 2km、…10km 所用的时间。

输出格式

两行,第一行是最短的时间,第二行是五个数据,分别是1到5号队员各自连续跑的公里数。

输入输出样例

输入 #1

333 700 1200 1710 2240 2770 3345 3956 4778 5899
300 610 960 1370 1800 2712 3734 4834 5998 7682
298 612 990 1540 2109 2896 3790 4747 5996 7654
289 577 890 1381 1976 2734 3876 5378 6890 9876
312 633 995 1407 1845 2634 3636 4812 5999 8123

输出 #1

9905
6 5 5 4 5

解题思路

对于这道题,如果使用暴力的全排列来做的话,那么显然时间复杂度会妥妥的达到10^5,如果我们想要过掉所有的数据点的话,暴力排列就显得十分无力,所以我们要选择别的方法。

这道题的特点在于要求最小值,因此我们可以往贪心和dp上去想,这里介绍一种贪心算法:

由于每个人都需要跑,因此第一步肯定要将每一个人分配一公里,那么接下来该怎么办呢?

显然无论在什么状态下,我们都要找跑这一公里最快的人来跑,因此我们只要每一次找每个人跑下一公里所需的时间再进行比较,就可以找到所需时间最短的人,将其标记即可。

或许你会问:每个人只能上场一次,如果按照刚刚的思路不就使得每个人上场多次了吗?

其实这并不是问题,由于我们要找的是最短的时间,因此无论先跑还是后跑,最优方案的总时长不变,所以不会对结果造成影响。

关于无后效性,由于每一步只受之前的状态影响,所以显然没有后效性。

最后有一个注意事项:开的标记数组不能超过10,否则会导致二维数组越界

AC:

#include<bits/stdc++.h>
using namespace std;
int minx=2147483647,flag,ans;
int a[5][11],b[5][11],c[5];
int main(){c[0]=c[1]=c[2]=c[3]=c[4]=1;for(int i=0;i<5;i++){for(int j=1;j<11;j++){cin>>a[i][j];b[i][j]=a[i][j]-a[i][j-1];}}for(int i=0;i<20;i++){minx=2147483647;for(int j=0;j<5;j++){if(b[j][c[j]+1]<minx&&c[j]+1<=10){flag=j;minx=b[j][c[j]+1];}}c[flag]++;}for(int i=0;i<5;i++){ans+=a[i][c[i]];}printf("%d\n%d %d %d %d %d\n",ans,c[0],c[1],c[2],c[3],c[4]);return 0; 
}

这篇关于【万题详解】洛谷P1252 马拉松接力赛的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


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

相关文章

使用Navicat工具比对两个数据库所有表结构的差异案例详解

《使用Navicat工具比对两个数据库所有表结构的差异案例详解》:本文主要介绍如何使用Navicat工具对比两个数据库test_old和test_new,并生成相应的DDLSQL语句,以便将te... 目录概要案例一、如图两个数据库test_old和test_new进行比较:二、开始比较总结概要公司存在多

css渐变色背景|<gradient示例详解

《css渐变色背景|<gradient示例详解》CSS渐变是一种从一种颜色平滑过渡到另一种颜色的效果,可以作为元素的背景,它包括线性渐变、径向渐变和锥形渐变,本文介绍css渐变色背景|<gradien... 使用渐变色作为背景可以直接将渐China编程变色用作元素的背景,可以看做是一种特殊的背景图片。(是作为背

springboot日期格式化全局LocalDateTime详解

《springboot日期格式化全局LocalDateTime详解》文章主要分析了SpringBoot中ObjectMapper对象的序列化和反序列化过程,并具体探讨了日期格式化问题,通过分析Spri... 目录分析ObjectMapper与jsonSerializer结论自定义日期格式(全局)扩展利用配置

Java中基于注解的代码生成工具MapStruct映射使用详解

《Java中基于注解的代码生成工具MapStruct映射使用详解》MapStruct作为一个基于注解的代码生成工具,为我们提供了一种更加优雅、高效的解决方案,本文主要为大家介绍了它的具体使用,感兴趣... 目录介绍优缺点优点缺点核心注解及详细使用语法说明@Mapper@Mapping@Mappings@Co

Python实现视频转换为音频的方法详解

《Python实现视频转换为音频的方法详解》这篇文章主要为大家详细Python如何将视频转换为音频并将音频文件保存到特定文件夹下,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录1. python需求的任务2. Python代码的实现3. 代码修改的位置4. 运行结果5. 注意事项

使用maven依赖详解

《使用maven依赖详解》本文主要介绍了Maven的基础知识,包括Maven的简介、仓库类型、常用命令、场景举例、指令总结、依赖范围、settings.xml说明等,同时,还详细讲解了Maven依赖的... 目录1. maven基础1.1 简介1.2 仓库类型1.3 常用命令1.4 场景举例1.5 指令总结

Java导出Excel动态表头的示例详解

《Java导出Excel动态表头的示例详解》这篇文章主要为大家详细介绍了Java导出Excel动态表头的相关知识,文中的示例代码简洁易懂,具有一定的借鉴价值,有需要的小伙伴可以了解下... 目录前言一、效果展示二、代码实现1.固定头实体类2.动态头实现3.导出动态头前言本文只记录大致思路以及做法,代码不进

Linux环境变量&&进程地址空间详解

《Linux环境变量&&进程地址空间详解》本文介绍了Linux环境变量、命令行参数、进程地址空间以及Linux内核进程调度队列的相关知识,环境变量是系统运行环境的参数,命令行参数用于传递给程序的参数,... 目录一、初步认识环境变量1.1常见的环境变量1.2环境变量的基本概念二、命令行参数2.1通过命令编程

Linux之进程状态&&进程优先级详解

《Linux之进程状态&&进程优先级详解》文章介绍了操作系统中进程的状态,包括运行状态、阻塞状态和挂起状态,并详细解释了Linux下进程的具体状态及其管理,此外,文章还讨论了进程的优先级、查看和修改进... 目录一、操作系统的进程状态1.1运行状态1.2阻塞状态1.3挂起二、linux下具体的状态三、进程的

一文详解Java Condition的await和signal等待通知机制

《一文详解JavaCondition的await和signal等待通知机制》这篇文章主要为大家详细介绍了JavaCondition的await和signal等待通知机制的相关知识,文中的示例代码讲... 目录1. Condition的核心方法2. 使用场景与优势3. 使用流程与规范基本模板生产者-消费者示例