【NOIP2018普及组复赛】题3:摆渡车

2024-06-02 10:20
文章标签 普及 noip2018 复赛 摆渡

本文主要是介绍【NOIP2018普及组复赛】题3:摆渡车,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题3:摆渡车

【题目描述】

n n n名同学要乘坐摆渡车从人大附中前往人民大学,第 i i i位同学在第 t i t_i ti分钟去等车。只有一辆摆渡车在工作,但摆渡车容量可以视为无限大。摆渡车从人大附中出发、把车上的同学送到人民大学、再回到人大附中(去接其他同学),这样往返一趟总共花费m分钟(同学上下车时间忽略不计)。摆渡车要将所有同学都送到人民大学。

凯凯很好奇,如果他能任意安排摆渡车出发的时间,那么这些同学的等车时间之和最小为多少呢?

注意:摆渡车回到人大附中后可以即刻出发。

【输入文件】

第一行包含两个正整数 n , m n,m nm,以一个空格分开,分别代表等车人数和摆渡车往返一趟的时间。

第二行包含 n n n个正整数,相邻两数之间以一个空格分隔,第 i i i个非负整数 t i t_i ti代表第 i i i个同学到达车站的时刻。

【输出文件】

输出一行,一个整数,表示所有同学等车时间之和的最小值(单位:分钟)。

【输入样例1】

5 1
3 4 4 3 5

【输出样例1】

0

【样例1说明】

同学 1 1 1和同学 4 4 4在第 3 3 3分钟开始等车,等待 0 0 0分钟,在第 3 3 3分钟乘坐摆渡车出发。摆渡车在第 4 4 4分钟回到人大附中。

同学 2 2 2和同学 3 3 3在第 4 4 4分钟开始等车,等待 0 0 0分钟,在第 4 4 4分钟乘坐摆渡车出发。摆渡车在第 5 5 5分钟回到人大附中。

同学 5 5 5在第 5 5 5分钟开始等车,等待 0 0 0分钟,在第 5 5 5分钟乘坐摆渡车出发。自此所有同学都被送到人民大学。总等待时间为 0 0 0

【输入样例1】

5 5
11 13 1 5 5

【输出样例1】

4

【样例2说明】

同学 3 3 3在第 1 1 1分钟开始等车,等待 0 0 0分钟,在第 1 1 1分钟乘坐摆渡车出发。摆渡车在第 6 6 6分钟回到人大附中。

同学 4 4 4和同学 5 5 5在第 5 5 5分钟开始等车,等待 1 1 1分钟,在第 6 6 6分钟乘坐摆渡车出发。摆渡车在第 11 11 11分钟回到人大附中。

同学 1 1 1在第 11 11 11分钟开始等车,等待 2 2 2分钟;同学 2 2 2在第 13 13 13分钟开始等车,等待 0 0 0分钟。他/她们在第 13 13 13分钟乘坐摆渡车出发。自此所有同学都被送到人民大学。

总等待时间为 4 4 4。可以证明,没有总等待时间小于 4 4 4的方案。

【数据规模】

对于 10 % 10\% 10% 的数据, n ≤ 10 , m = 1 , 0 ≤ t i ≤ 100 n≤10,m=1,0≤t_i≤100 n10,m=1,0ti100

对于 30 % 30\% 30% 的数据, n ≤ 20 , m ≤ 2 , 0 ≤ t i ≤ 100 n≤20,m≤2,0≤t_i≤100 n20,m2,0ti100

对于 50 % 50\% 50% 的数据, n ≤ 500 , m ≤ 100 , 0 ≤ t i ≤ 1 0 4 n≤500,m≤100,0≤t_i≤10^4 n500,m100,0ti104

另有 20 % 20\% 20% 的数据, n ≤ 500 , m ≤ 10 , 0 ≤ t i ≤ 4 × 1 0 6 n≤500,m≤10,0≤t_i≤4×10^6 n500,m10,0ti4×106

对于 100 % 100\% 100% 的数据, n ≤ 500 , m ≤ 100 , 0 ≤ t i ≤ 4 × 1 0 6 n≤500,m≤100,0≤t_i≤4×10^6 n500,m100,0ti4×106

【代码如下】:

#include <bits/stdc++.h>
using namespace std;
const int maxT = 4000105;
int n, m, t, ti, ans = 1e9, cnt[maxT], sum[maxT], f[maxT];
int main() {scanf("%d%d", &n, &m);for (int i = 1; i <= n; i++) {scanf("%d", &ti);t = max(t, ti);cnt[ti]++;sum[ti] += ti;}for (int i = 1; i < t + m; i++) {cnt[i] += cnt[i - 1];sum[i] += sum[i - 1];} for (int i = 0; i < t + m; i++) {if (i >= m && cnt[i - m] == cnt[i]) {f[i] = f[i - m];continue;} f[i] = cnt[i] * i - sum[i]; for (int j = max(i - m - m + 1, 0); j <= i - m; j++) {f[i] = min(f[i], f[j] + (cnt[i] - cnt[j]) * i - (sum[i] - sum[j]));}}for (int i = t; i < t + m; i++) {ans = min(ans, f[i]);}printf("%d\n", ans);return 0;
}

这篇关于【NOIP2018普及组复赛】题3:摆渡车的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

笔试强训,[NOIP2002普及组]过河卒牛客.游游的水果大礼包牛客.买卖股票的最好时机(二)二叉树非递归前序遍历

目录 [NOIP2002普及组]过河卒 牛客.游游的水果大礼包 牛客.买卖股票的最好时机(二) 二叉树非递归前序遍历 [NOIP2002普及组]过河卒 题里面给的提示很有用,那个马的关系,后面就注意,dp需要作为long的类型。 import java.util.Scanner;// 注意类名必须为 Main, 不要有任何 package xxx 信息publ

百度之星 2015 复赛 1001 (数长方形)

数长方形    Accepts: 595    Submissions: 1225  Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Problem Description 小度熊喜欢玩木棒。一天他在玩木棒的时候,发现一些木棒会形成长方形

CSP-J/S 复赛程序提交指南,提交错误必爆零!!!

CSP-J/S 复赛题目程序需要以文件的形式提交,如果之前没有了解过,那肯定会爆0,该怎么操作呢? 大家好,我是大李。 针对复赛考试提交详情,这里做个详细介绍,分为文件的创建和文件体提交等事项。 一、关于文件建立 复赛考试时需要根据提示,在桌面建立文件夹,将含有文件体的cpp文件保存至桌面。 每一题的命名都需要根据提示来去命名。 以2023年CSP-J/S 第二轮为例 在电

信息学奥赛初赛天天练-83-NOIP2014普及组-基础题2-输入设备、输出设备、操作系统、二进制、整数除法、while、do while循环

1 NOIP 2014 普及组 基础题2 4 以下哪一种设备属于输出设备( ) A 扫描仪 B 键盘 C 鼠标 D 打印机 5 下列对操作系统功能的描述最为完整的是( ) A 负责外设与主机之间的信息交换 B 负责诊断机器的故障 C 控制和管理计算机系统的各种硬件和软件资源的使用 D 将没有程序编译成目标程序 11 下列各无符号十进制整数中,能用八位二进制表示的数中最大的是( ) A 296

免费SSL证书大全,加速普及网站实现HTTPS加密

免费SSL证书大全,加速普及网站实现HTTPS加密   SSL 证书用于加密 HTTP 协议,实现网站通过HTTPS加密协议访问。随着国内外各大网站实现全站 HTTPS 协议,以及搜索引擎对使用 HTTPS 协议网站的更加友好,加之互联网对数据和隐私安全的加强,网站添加 SSL 证书并实现 HTTPS 加密协议访问已经成为趋势和必然。 SSL证书大全​zzzjtd.com 而对于给网站添加

重生之当IT管理员遇到数据摆渡界“悟空”

您可以搜索“飞驰云联”了解更多信息。 关于飞驰云联 飞驰云联是中国领先的数据安全传输解决方案提供商,长期专注于安全可控、性能卓越的数据传输技术和解决方案,公司产品和方案覆盖了跨网跨区域的数据安全交换、供应链数据安全传输、数据传输过程的防泄漏、FTP的增强和国产化替代、文件传输自动化和传输集成等各种数据传输场景。飞驰云联主要服务于集成电路半导体、先进制造、高科技、金融、政府机构等行业的中大型

讨论运维监控工具的普及程度

在讨论运维监控工具的普及程度时,加入PIGOSS BSM产品的分析是非常有意义的,因为PIGOSS BSM是一款在中国市场具有一定影响力的运维监控工具。 PIGOSS BSM运维监控工具是一款综合性的IT运维监控解决方案,它能够对多层次的IT资源进行监测,包括但不限于性能监测、事件管理、报表管理等功能模块。PIGOSS BSM的一个独特之处在于其拓扑关联配置工具,这使得用户可以根据自身的I

P2239 [NOIP2014 普及组] 螺旋矩阵

P2239 [NOIP2014 普及组] 螺旋矩阵 50分 //O(n^2)复杂度,能算n<=10000的 #include <bits/stdc++.h>using namespace std;//row当前行, column当前列, left:左边界,righ:右边界,top:上边界,bottom:下边界 int n, x, y, ans, row=1, column=0, lef,

信息学奥赛初赛天天练-80-NOIP2015普及组-基础题5-错位排列、二叉树、完全二叉树、叶子节点、完全二叉树叶子节点

NOIP 2015 普及组 基础题5 21 重新排列 1234使得每一个数字都不在原来的位置上,一共有( )种排法 22 一棵结点数为 2015的二叉树最多有( )个叶子结点 2 相关知识点 1) 错位排列 考虑一个有n个元素的排列,若一个排列中所有的元素都不在自己原来的位置上,那么这样的排列就称为原排列的一个错排。 n个元素的错排数记为D(n) 错排问题最早被尼古拉·伯努利和欧拉研究

信息学奥赛初赛天天练-79-NOIP2015普及组-基础题4-即时通讯软件、二叉树遍历、前序遍历、中序遍历、后序遍历、算法时间复杂度

NOIP 2015 普及组 基础题4 11 下面哪种软件不属于即时通信软件( ) A QQ B MSN C 微信 D P2P 16 前序遍历序列与中序遍历序列相同的二叉树为( ) A 根结点无左子树 B 根结点无右子树 C 只有根结点的二叉树或非叶子结点只有左子树的二叉树 D 只有根结点的二叉树或非叶子结点只有右子树的二叉树 18 下列选项中不属于视频文件格式的是( ) A TXT B AV