当前位置: 首页 > news >正文

奶牛用餐 优先队列 java

👨‍🏫 奶牛用餐

约翰的农场有 n n n 头奶牛,编号 1 s i m n 1 \\sim n 1simn

每天奶牛们都要去食堂用餐。

食堂一共有 k k k 个座位,也就是说同一时间最多可以容纳 k k k 头奶牛同时用餐。

已知,第 i i i 头奶牛到达食堂的具体时刻为 s _ i s\_i s_i,用餐所需花费的时间为 t _ i t\_i t_i

保证 s _ 1 < s _ 2 < … < s _ n s\_1 < s\_2 < … < s\_n s_1<s_2<<s_n

为了让奶牛们有序用餐,约翰制定了如下规则:

  • 每头奶牛都必须由约翰安排座位用餐。
  • 每头奶牛从到达食堂的那一刻起,即刻进入待安排状态。
  • 任意时刻,只要存在空座位以及待安排奶牛,约翰就会即刻安排奶牛就座用餐。
  • 如果某一时刻,空座位的数量少于待安排奶牛的数量,则优先安排编号更小的奶牛就座用餐。
  • 每头奶牛用餐完毕的那一时刻都会被约翰立即轰走,即刻空出座位。

除了用餐花费时间以外,其它花费时间忽略不计。

请你计算并输出,每头奶牛用餐完毕的具体时刻。

输入格式

第一行包含两个整数 n , k n,k n,k

接下来 n n n 行,其中第 i i i 行包含两个整数 s _ i , t _ i s\_i,t\_i s_i,t_i

注意,输入保证 s _ 1 < s _ 2 < … < s _ n s\_1 < s\_2 < … < s\_n s_1<s_2<<s_n

输出格式

n n n 行,每行输出一个整数,其中第 i i i 行的整数表示第 i i i 头奶牛用餐完毕的具体时刻。

数据范围

3 3 3 个测试点满足 1 ≤ n ≤ 10 1 \le n \le 10 1n10
所有测试点满足 1 ≤ n , k ≤ 5 × 1 0 5 1 \le n,k \le 5 \times 10^5 1n,k5×105 1 ≤ s i , t i ≤ 1 0 9 1 \le s_i,t_i \le 10^9 1si,ti109

输入样例1:

3 2
1 5
2 5
3 5

输出样例1:

6
7
11

输入样例2:

6 1
1 1000000000
2 1000000000
3 1000000000
4 1000000000
5 1000000000
6 3

输出样例2:

1000000001
2000000001
3000000001
4000000001
5000000001
5000000004

🍺 AC code


import java.io.*;
import java.util.*;public class Main
{static int N = 500050;static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));static BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));public static void main(String[] args) throws IOException{
//		Scanner sc = new Scanner(System.in);
//		int n = sc.nextInt();
//		int m = sc.nextInt();String[] ss = in.readLine().split(" ");int n = Integer.parseInt(ss[0]);int m = Integer.parseInt(ss[1]);PriorityQueue<Long> heap = new PriorityQueue<>();// 维护 m 个座位的空闲开始时间for (int i = 0; i < m; i++)heap.add(0L);// 座位的空闲时间初始化为 0while (n-- > 0){
//			long start = sc.nextLong();
//			long time = sc.nextLong();ss = in.readLine().split(" ");long start = Long.parseLong(ss[0]);long time = Long.parseLong(ss[1]);long t = heap.poll();// 每次获取最快有空位的时间long end = Math.max(start, t) + time;// 和自身的到达时间取 max 值heap.add(end);// 把此座位的下一次空位时刻加入 堆System.out.println(end);}}
}

相关文章:

奶牛用餐 优先队列 java

&#x1f468;‍&#x1f3eb; 奶牛用餐 约翰的农场有 n n n 头奶牛&#xff0c;编号 1 s i m n 1 \\sim n 1simn。 每天奶牛们都要去食堂用餐。 食堂一共有 k k k 个座位&#xff0c;也就是说同一时间最多可以容纳 k k k 头奶牛同时用餐。 已知&#xff0c;第 i i i …...

包管理机制pip3

pip3 安装pip3 安装pip3 apt install python3-pip yum install python3-pip从仓库出发的命令 查询仓库信息 // 获取默认pip3源 pip3 config get global.index-url查询所有软件包 查询已经安装的所有软件包 pip3 list从软件包出发的命令 从软件包名出发查询其他信息 查询…...

liunx在线安装tomcat

1、在线安装 https://dlcdn.apache.org/tomcat/tomcat-8/v8.5.91/bin/apache-tomcat-8.5.91.tar.gz 执行&#xff1a;wget --no-check-certificate https://dlcdn.apache.org/tomcat/tomcat-8/v8.5.91/bin/apache-tomcat-8.5.91.tar.gz ps:或者直接把tar.gz扔服务器 2、 编…...

导入示例工程出现error: failed to start ability. Error while Launching activity错误的解决办法

导入华为健康生活应用&#xff08;ArkTS&#xff09;&#xff0c;使用DevEco Studio打开&#xff0c;运行报错&#xff1a; error: failed to start ability. Error while Launching activity解决办法&#xff1a;修改module.json5里面exported的值&#xff0c;由false改为tr…...

【深入了解PyTorch】PyTorch分布式训练:多GPU、数据并行与模型并行

【深入了解PyTorch】PyTorch分布式训练:多GPU、数据并行与模型并行 PyTorch分布式训练:多GPU、数据并行与模型并行1. 分布式训练简介2. 多GPU训练3. 数据并行4. 模型并行5. 总结PyTorch分布式训练:多GPU、数据并行与模型并行 在深度学习领域,模型的复杂性和数据集的巨大规…...

linux 下 网卡命名改名

Linux 操作系统的网卡设备的传统命名方式是 eth0、eth1、eth2等&#xff0c;而 CentOS7 提供了不同的命名规则&#xff0c;默认是网卡命名会根据网卡的硬件信息&#xff0c;插槽位置等有关&#xff1b;来分配。这样做的优点是命名全自动的、可预知的&#xff0c;缺点是比 eth0、…...

6.2.0在线编辑:GrapeCity Documents for Word (GcWord) Crack

GrapeCity Word 文档 (GcWord) 支持 Office Math 函数以及转换为 MathML GcWord 现在支持在 Word 文档中创建和编辑 Office Math 内容。GcWord 中的 OMath 支持包括完整的 API&#xff0c;可处理科学、数学和通用 Word 文档中广泛使用的数学符号、公式和方程。以下是通过 OMa…...

为什么需要智能指针?

为什么需要智能指针&#xff1f; 解决忘记释放内存导致内存泄漏的问题。解决异常安全问题。 #include<iostream> using namespace std;int div() {int a, b;cin >> a >> b;if (b 0)throw invalid_argument("除0错误");return a / b; } void Func(…...

《华为认证》L2TP VPN配置

配置接口ip地址&#xff0c;并且将防火墙的接口加入对应的安全区域 。 LNS的G1/0/0 IP为202.1.1.1 1、配置LNS的缺省路由&#xff1a; ip route-static 0.0.0.0 0.0.0.0 202.1.1.2 2、通过WEB 界面配置防火墙的 L2TP VPN 浏览器输入&#xff1a; https://202.1.1.1:8443/def…...

【JVM】JVM垃圾收集器

文章目录 什么是JVM垃圾收集器四种垃圾收集器&#xff08;按类型分&#xff09;1.串行垃圾收集器(效率低&#xff09;2.并行垃圾收集器(JDK8默认使用此垃圾回收器&#xff09;3.CMS&#xff08;并发&#xff09;垃圾收集器(只针对老年代垃圾回收的&#xff09; 什么是JVM垃圾收…...

StarGANv2: Diverse Image Synthesis for Multiple Domains论文解读及实现(一)

StarGAN v2: Diverse Image Synthesis for Multiple Domainsp github:https://github.com/clovaai/stargan-v2 1 模型架构 模型主要架构由四部分组成 ①Generator、②Mapping network、③Style encoder、④Discriminator Generator&#xff1a;G网络 生成模型G将输入图片x转换…...

Go Gin 中使用 JWT

一、JWT JWT全称JSON Web Token是一种跨域认证解决方案&#xff0c;属于一个开放的标准&#xff0c;它规定了一种Token实现方式&#xff0c;目前多用于前后端分离项目和OAuth2.0业务场景下。 二、为什么要用在你的Gin中使用JWT 传统的Cookie-Sesson模式占用服务器内存, 拓展性…...

AWS中Lambda集成SNS

1.创建Lambda 在Lambda中&#xff0c;创建名为AWSSNSDemo的函数 use strict console.log(loading function); var aws require(aws-sdk); var docClient new aws.DynamoDB.DocumentClient(); aws.config.regionap-southeast-1;exports.handler function(event,context,cal…...

Mac下⬇️Git如何下载/上传远程仓库

使用终端检查电脑是否安装Git git --version 通过此文章安装Git ➡️ ​​​​​​​传送门&#x1f310; 方式1⃣️使用终端操作 1.下载——克隆远程仓库到本地 git clone [远程地址] 例&#xff1a;git clone https://gitee.com/lcannal/movie.git​ 2.编…...

linux 命令--常用关机命令

1.使用shutdown命令 shutdown命令是Linux系统下最常用的关机命令之一。它可以让系统在指定时间内进行关机或者重启操作。例如&#xff0c;下面的命令可以让系统在5分钟后进行关机操作&#xff1a; sudo shutdown -h5其中&#xff0c;“-h”表示关机&#xff0c;“5”表示5分钟…...

ttf-dejavu fontconfig字体

ttf-dejavu fontconfig是验证码&#xff0c;pdf&#xff0c;excel时需要用到的字体 编辑dockerfile&#xff0c;先切换国内镜像源&#xff0c;默认alpinelinux是国外源&#xff0c;下载包会很慢 vim Dockerfile FROM alpine:latest RUN sed -i s/dl-cdn.alpinelinux.org/mirr…...

Open3D点云数据处理(十九):最小二乘直线拟合(矩阵方程法)

文章目录 1 最小二乘直线拟合原理(矩阵方程角度)2 相关知识2.1 超定线性方程组2.2 正规方程2.3 奇异值分解3 最小二乘直线拟合代码实现4 点云最小二乘直线拟合5 相关链接专栏目录:Open3D点云数据处理(Python) 1 最小二乘直线拟合原理(矩阵方程角度) 最小二乘直线拟合是…...

数据库事务ACID介绍

一、ACID简介 ACID&#xff0c;是指数据库管理系统&#xff08;DBMS&#xff09;在增删改数据的的过程中&#xff0c;为保证事务&#xff08;transaction&#xff09;的准确性&#xff0c;可靠性等&#xff0c;所必须具备的四个特性&#xff1a;原子性&#xff08;atomicity&a…...

SM8650 qcxserver.c STRM_Initialize

STRM_Initialize streammanager 初始化流程 目录 STRM_Initialize Gptp::Init Config::Init SensorManager::Init SensorPlatform::SensorPlatformInit SensorManager::LoadSensorLib SensorManager::OpenSensorLib SensorManager::DetectAll SensorManager::DetectHandlerT…...

适配器模式-java实现

意图 复用已经存在的接口&#xff0c;与所需接口不一致的类。即将一个类&#xff08;通常是旧系统中的功能类&#xff09;&#xff0c;通过适配器转化成另一个接口的实现。&#xff08;简单来说&#xff0c;就是复用旧系统的功能&#xff0c;去实现新的接口&#xff09; 我们举…...

XML Group端口详解

在XML数据映射过程中&#xff0c;经常需要对数据进行分组聚合操作。例如&#xff0c;当处理包含多个物料明细的XML文件时&#xff0c;可能需要将相同物料号的明细归为一组&#xff0c;或对相同物料号的数量进行求和计算。传统实现方式通常需要编写脚本代码&#xff0c;增加了开…...

突破不可导策略的训练难题:零阶优化与强化学习的深度嵌合

强化学习&#xff08;Reinforcement Learning, RL&#xff09;是工业领域智能控制的重要方法。它的基本原理是将最优控制问题建模为马尔可夫决策过程&#xff0c;然后使用强化学习的Actor-Critic机制&#xff08;中文译作“知行互动”机制&#xff09;&#xff0c;逐步迭代求解…...

Python:操作 Excel 折叠

💖亲爱的技术爱好者们,热烈欢迎来到 Kant2048 的博客!我是 Thomas Kant,很开心能在CSDN上与你们相遇~💖 本博客的精华专栏: 【自动化测试】 【测试经验】 【人工智能】 【Python】 Python 操作 Excel 系列 读取单元格数据按行写入设置行高和列宽自动调整行高和列宽水平…...

遍历 Map 类型集合的方法汇总

1 方法一 先用方法 keySet() 获取集合中的所有键。再通过 gey(key) 方法用对应键获取值 import java.util.HashMap; import java.util.Set;public class Test {public static void main(String[] args) {HashMap hashMap new HashMap();hashMap.put("语文",99);has…...

vscode(仍待补充)

写于2025 6.9 主包将加入vscode这个更权威的圈子 vscode的基本使用 侧边栏 vscode还能连接ssh&#xff1f; debug时使用的launch文件 1.task.json {"tasks": [{"type": "cppbuild","label": "C/C: gcc.exe 生成活动文件"…...

2024年赣州旅游投资集团社会招聘笔试真

2024年赣州旅游投资集团社会招聘笔试真 题 ( 满 分 1 0 0 分 时 间 1 2 0 分 钟 ) 一、单选题(每题只有一个正确答案,答错、不答或多答均不得分) 1.纪要的特点不包括()。 A.概括重点 B.指导传达 C. 客观纪实 D.有言必录 【答案】: D 2.1864年,()预言了电磁波的存在,并指出…...

JUC笔记(上)-复习 涉及死锁 volatile synchronized CAS 原子操作

一、上下文切换 即使单核CPU也可以进行多线程执行代码&#xff0c;CPU会给每个线程分配CPU时间片来实现这个机制。时间片非常短&#xff0c;所以CPU会不断地切换线程执行&#xff0c;从而让我们感觉多个线程是同时执行的。时间片一般是十几毫秒(ms)。通过时间片分配算法执行。…...

汇编常见指令

汇编常见指令 一、数据传送指令 指令功能示例说明MOV数据传送MOV EAX, 10将立即数 10 送入 EAXMOV [EBX], EAX将 EAX 值存入 EBX 指向的内存LEA加载有效地址LEA EAX, [EBX4]将 EBX4 的地址存入 EAX&#xff08;不访问内存&#xff09;XCHG交换数据XCHG EAX, EBX交换 EAX 和 EB…...

ABAP设计模式之---“简单设计原则(Simple Design)”

“Simple Design”&#xff08;简单设计&#xff09;是软件开发中的一个重要理念&#xff0c;倡导以最简单的方式实现软件功能&#xff0c;以确保代码清晰易懂、易维护&#xff0c;并在项目需求变化时能够快速适应。 其核心目标是避免复杂和过度设计&#xff0c;遵循“让事情保…...

LINUX 69 FTP 客服管理系统 man 5 /etc/vsftpd/vsftpd.conf

FTP 客服管理系统 实现kefu123登录&#xff0c;不允许匿名访问&#xff0c;kefu只能访问/data/kefu目录&#xff0c;不能查看其他目录 创建账号密码 useradd kefu echo 123|passwd -stdin kefu [rootcode caozx26420]# echo 123|passwd --stdin kefu 更改用户 kefu 的密码…...