消息队列之卡夫卡 + EFLFK集群部署

2023-10-13 13:40

本文主要是介绍消息队列之卡夫卡 + EFLFK集群部署,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Zookeeper 定义

Zookeeper是一个开源的分布式的,为分布式框架提供协调服务的Apache项目。

1.2 Zookeeper 工作机制

Zookeeper从设计模式角度来理解:是一个基于观察者模式设计的分布式服务管理框架,它负责存储和管理大家都关心的数据,然后接受观察者的注册,一旦这些数据的状态发生变化,Zookeeper就将负责通知已经在Zookeeper上注册的那些观察者做出相应的反应。

也就是说 Zookeeper = 文件系统 + 通知机制。

Zookeeper 特点
(1)Zookeeper:一个领导者(Leader),多个跟随者(Follower)组成的集群。

(2)Zookeepe集群中只要有半数以上节点存活,Zookeeper集群就能正常服务。所以Zookeeper适合安装奇数台服务器。

(3)全局数据一致:每个Server保存一份相同的数据副本,Client无论连接到哪个Server,数据都是一致的。

(4)更新请求顺序执行,来自同一个Client的更新请求按其发送顺序依次执行,即先进先出。

(5)数据更新原子性,一次数据更新要么成功,要么失败。

(6)实时性,在一定时间范围内,Client能读到最新数据。

Zookeeper 数据结构
ZooKeeper数据模型的结构与Linux文件系统很类似,整体上可以看作是一棵树,每个节点称做一个ZNode。每一个ZNode默认能够存储1MB的数据,每个ZNode都可以通过其路径唯一标识。

1.5 Zookeeper 应用场景
提供的服务包括:统一命名服务、统一配置管理、统一集群管理、服务器节点动态上下线、软负载均衡等。

1.5.1 统一命名服务
在分布式环境下,经常需要对应用/服务进行统一命名,便于识别。例如:IP不容易记住,而域名容易记住。

1.5.2 统一配置管理
(1)分布式环境下,配置文件同步非常常见。一般要求一个集群中,所有节点的配置信息是一致的,比如Kafka集群。对配置文件修改后,希望能够快速同步到各个节点上。

(2)配置管理可交由ZooKeeper实现。可将配置信息写入ZooKeeper上的一个Znode。各个客户端服务器监听这个Znode。一旦 Znode中的数据被修改,ZooKeeper将通知各个客户端服务器。

1.5.3 统一集群管理
(1)分布式环境中,实时掌握每个节点的状态是必要的。可根据节点实时状态做出一些调整。

(2)ZooKeeper可以实现实时监控节点状态变化。可将节点信息写入ZooKeeper上的一个ZNode。监听这个ZNode可获取它的实时状态变化。

1.5.4 服务器动态上下线
客户端能实时洞察到服务器上下线的变化。

1.5.5 软负载均衡
在Zookeeper中记录每台服务器的访问数,让访问数最少的服务器去处理最新的客户端请求。

1.6 Zookeeper 选举机制
1.6.1 第一次启动选举机制
假设有5台服务器:

(1)服务器1启动,发起一次选举。服务器1投自己一票。此时服务器1票数一票,不够半数以上(3票),选举无法完成,服务器1状态保持为LOOKING;

(2)服务器2启动,再发起一次选举。服务器1和2分别投自己一票并交换选票信息:此时服务器1发现服务器2的myid比自己目前投票推举的(服务器1)大,更改选票为推举服务器2。此时服务器1票数0票,服务器2票数2票,没有半数以上结果,选举无法完成,服务器1,2状态保持LOOKING。

(3)服务器3启动,发起一次选举。此时服务器1和2都会更改选票为服务器3。此次投票结果:服务器1为0票,服务器2为0票,服务器3为3票。此时服务器3的票数已经超过半数,服务器3当选Leader。服务器1,2更改状态为FOLLOWING,服务器3更改状态为LEADING;

(4)服务器4启动,发起一次选举。此时服务器1,2,3已经不是LOOKING状态,不会更改选票信息。交换选票信息结果:服务器3为3票,服务器4为1票。此时服务器4服从多数,更改选票信息为服务器3,并更改状态为FOLLOWING;

(5)服务器5启动,和服务器4一样当小弟。

非第一次启动选举机制

1、当ZooKeeper 集群中的一台服务器出现以下两种情况之一时,就会开始进入Leader选举:

(1)服务器初始化启动。

(2)服务器运行期间无法和Leader保持连接。

2、而当一台机器进入Leader选举流程时,当前集群也可能会处于以下两种状态:

(1)集群中本来就已经存在一个Leader。

  • 对于已经存在Leader的情况,机器试图去选举Leader时,会被告知当前服务器的Leader信息,对于该机器来说,仅仅需要和 Leader机器建立连接,并进行状态同步即可。

(2)集群中确实不存在Leader。

  • 假设ZooKeeper由5台服务器组成,SID分别为1、2、3、4、5,ZXID分别为8、8、8、7、7,并且此时SID为3的服务器是Leader。某一时刻,3和5服务器出现故障,因此开始进行Leader选举。

  • 选举Leader规则:

    1. EPOCH大的直接胜出
    2. EPOCH相同,事务id大的胜出
    3. 事务id相同,服务器id大的胜出

小贴士:

  • SID:服务器ID。用来唯一标识一台ZooKeeper集群中的机器,每台机器不能重复,和myid一致。
  • ZXID:事务ID。ZXID是一个事务ID,用来标识一次服务器状态的变更。在某一时刻,集群中的每台机器的ZXID值不一定完全一致,这和ZooKeeper服务器对于客户端“更新请求”的处理逻辑速度有关。
  • Epoch:每个Leader任期的代号。没有Leader时同一轮投票过程中的逻辑时钟值是相同的。每投完一次票这个数据就会增加。

实验

准备 3 台服务器做 Zookeeper 集群:

192.168.180.10

192.168.180.20

192.168.180.30

写一个安装脚本

在server1上写一个安装脚本,用于安装Zookeeper。

vim /yujish/zookeeper001.sh

#!/bin/bash  #部署Zookeeper集群,server1的安装脚本  ​  

##1.安装前准备  

#关闭防火墙  systemctl stop firewalld

 systemctl disable firewalld  

setenforce 0  ​  #安装 JDK 环境。

如果服务器无法连接外网,需要先搭建本地yum仓库  yum install -y java-1.8.0-openjdk java-1.8.0-openjdk-devel  java -version  ​  #zookeeper下载安装包  

#官方下载地址:https://archive.apache.org/dist/zookeeper/  ​

 #wget命令是Linux系统用于从Web下载文件的命令行工具,服务器联通外网的情况下,可使用此种方法下载软件包。如果服务器无法连接外网,需要提前准备好软件包,放入/opt/目录下。  cd /opt/  wget https://archive.apache.org/dist/zookeeper/zookeeper-3.5.7/apache-zookeeper-3.5.7-bin.tar.gz  ​  

##2.安装 Zookeeper。提前将zookeeper的安装包传到/opt/目录下。  

cd /opt/  

tar -zxvf apache-zookeeper-3.5.7-bin.tar.gz  

mv apache-zookeeper-3.5.7-bin /usr/local/zookeeper-3.5.7  ​  

##3.修改配置文件

 cd /usr/local/zookeeper-3.5.7/conf/  

cp zoo_sample.cfg zoo.cfg  ​

 #修改第12行,指定保存Zookeeper中的数据的目录,目录需要单独创建

 sed -i '12c dataDir=/usr/local/zookeeper-3.5.7/data' /usr/local/zookeeper-3.5.7/conf/zoo.cfg  #在第12行下方添加内容,指定存放日志的目录,目录需要单独创建

 sed -i '12a dataLogDir=/usr/local/zookeeper-3.5.7/logs' /usr/local/zookeeper-3.5.7/conf/zoo.cfg  #36行,在配置文件中添加集群信息。集群节点通信时使用端口3188,选举leader时使用的端口3288。  

echo "server.1=192.168.180.10:3188:3288

 server.2=192.168.180.20:3188:3288  

server.3=192.168.180.30:3188:3288" >> /usr/local/zookeeper-3.5.7/conf/zoo.cfg  ​  #在每个节点上创建数据目录和日志目录

 mkdir /usr/local/zookeeper-3.5.7/data  

mkdir /usr/local/zookeeper-3.5.7/logs  ​  #在每个节点的dataDir指定的目录下创建一个 myid 的文件,注意每个节点的myid不能相同  

echo 1 > /usr/local/zookeeper-3.5.7/data/myid  ​  ​  

##4.配置 Zookeeper 启动脚本,将zookeeper加入系统服务管理  

cat <<EOF > /etc/init.d/zookeeper  

#!/bin/bash  

#chkconfig:2345 20 90  

#description:Zookeeper Service Control Script  

ZK_HOME='/usr/local/zookeeper-3.5.7'  case $1 in  start)      

echo

"---------- zookeeper 启动 ------------"    

 $ZK_HOME/bin/zkServer.sh start    

;;  

stop)    

echo

"---------- zookeeper 停止 ------------"      

$ZK_HOME/bin/zkServer.sh stop    

;;  

restart)      

echo

"---------- zookeeper 重启 ------------"      

$ZK_HOME/bin/zkServer.sh restart    

;;  

status)      

echo

"---------- zookeeper 状态 ------------"      

$ZK_HOME/bin/zkServer.sh status    

;;  

*)      

echo "Usage: $0 {start|stop|restart|status}"  

esac  

EOF  ​  #为脚本增加执行权限。添加到启动服务,设置为开机自启。

 chmod +x /etc/init.d/zookeeper  

chkconfig --add zookeeper  #chkconfig --list zookeeper 可查看启动服务

配置文件zoo.cfg注释:

 tickTime=2000   #通信心跳时间,Zookeeper服务器与客户端心跳时间,单位毫秒  

initLimit=10    

#Leader和Follower初始连接时能容忍的最多心跳数(tickTime的数量),这里表示为10*2s  syncLimit=5     #Leader和Follower之间同步通信的超时时间,这里表示如果超过5*2s,Leader认为Follwer死掉,并从服务器列表中删除Follwer  

dataDir=/usr/local/zookeeper-3.5.7/data      #修改,指定保存Zookeeper中的数据的目录,目录需要单独创建  

dataLogDir=/usr/local/zookeeper-3.5.7/logs   #添加,指定存放日志的目录,目录需要单独创建  clientPort=2181   #客户端连接端口  #添加集群信息  

server.1=192.168.180.10:3188:3288  

server.2=192.168.180.20:3188:3288  

server.3=192.168.180.30:3188:3288 #集群节点通信时使用端口3188,选举leader时使用的端口3288

 server.A=B:C:D

 ●A是一个数字,表示这个是第几号服务器。集群模式下需要在zoo.cfg中dataDir指定的目录下创建一个文件myid,这个文件里面有一个数据就是A的值,Zookeeper启动时读取此文件,拿到里面的数据与zoo.cfg里面的配置信息比较从而判断到底是哪个server。  

●B是这个服务器的地址。  

●C是这个服务器Follower与集群中的Leader服务器交换信息的端口。  ●D是万一集群中的Leader服务器挂了,需要一个端口来重新进行选举,选出一个新的Leader,而这个端口就是用来执行选举时服务器相互通信的端口。

写第二个脚本(用于传输和执行脚本)

在server1写第二个脚本,用于将安装脚本传给给server2和server3,并执行脚本和启动服务。

vim /yujish/zk.sh

#!/bin/bash  

#descripe:该脚本用于传输和执行zookeeper的安装脚本。

即在server1上,将安装脚本传给server2、server3,并修改myid。之后依次执行。  ​  

#root密码  

pass=1234  

#三台服务器的ip  

ip1=192.168.180.10  

ip2=192.168.180.20  

ip3=192.168.180.30  ​  

#复制脚本并命名为002,将myid修改为2。用于传给server2执行。  

cp /yujish/zookeeper001.sh /yujish/zookeeper002.sh  

sed -i '/zookeeper-3.5.7/data/myid/c

echo 2>/usr/local/zookeeper-3.5.7/data/myid  

' /yujish/zookeeper002.sh  ​  

#安装expect工具

 yum install -y expect  ​  #将002脚本传给server2

 /usr/bin/expect <<-EOF  

spawn scp /yujish/zookeeper002.sh ${ip2}:/yujish/

 expect {          

"(yes/no)" {send "yes\n"; exp_continue}          

"password" {send "$pass\n"}  

}  

EOF

 ​  #复制脚本并命名为003,修改myid为3。用于传给server3执行。  

cp /yujish/zookeeper001.sh /yujish/zookeeper003.sh  

sed -i '/zookeeper-3.5.7/data/myid/c echo 3>/usr/local/zookeeper-3.5.7/data/myid   ' /yujish/zookeeper003.sh  ​  

#将003脚本传给server3  

/usr/bin/expect <<-EOF  

spawn scp /yujish/zookeeper003.sh ${ip3}:/yujish/  

expect {          

"(yes/no)" {send "yes\n"; exp_continue}          

"password" {send "$pass\n"}  

}  

EOF  ​  

#执行server1中的脚本,安装zookeeper  

bash /yujish/zookeeper001.sh  ​  

#执行server2中的脚本,安装zookeeper  

/usr/bin/expect <<-EOF  

spawn ssh ${ip2} bash /yujish/zookeeper002.sh  

expect {          

"(yes/no)" {send "yes\n"; exp_continue}          

"password" {send "$pass\n"}  

}  

EOF  ​  

#执行server3中的脚本,安装zookeeper  

/usr/bin/expect <<-EOF  

spawn ssh ${ip3} bash /yujish/zookeeper003.sh  

expect {          

"(yes/no)" {send "yes\n"; exp_continue}          

"password" {send "$pass\n"}  

}  

EOF  ​  

#启动server1中的zookeeper  service zookeeper start  ​

 #启动server2中的zookeeper  

/usr/bin/expect <<-EOF

spawn ssh ${ip2} service zookeeper start

expect {          

"(yes/no)" {send "yes\n"; exp_continue}          

"password" {send "$pass\n"}  

}  

EOF  ​  

#启动server3中的zookeeper  

/usr/bin/expect <<-EOF  

spawn ssh ${ip3} service zookeeper start  

expect {          

"(yes/no)" {send "yes\n"; exp_continue}          

"password" {send "$pass\n"}  

}  

EOF

执行第二个脚本进行安装

 bash /yujish/zk.sh

Kafka 定义

Kafka 是一个分布式的基于发布/订阅模式的消息队列(MQ,Message Queue),主要应用于大数据实时处理领域。

4.2 Kafka 简介

Kafka 是最初由 Linkedin 公司开发,是一个分布式、支持分区的(partition)、多副本的(replica),基于 Zookeeper 协调的分布式消息中间件系统,它的最大的特性就是可以实时的处理大量数据以满足各种需求场景,比如基于 hadoop 的批处理系统、低延迟的实时系统、Spark/Flink 流式处理引擎,nginx 访问日志,消息服务等等,用 scala 语言编写, Linkedin 于 2010 年贡献给了 Apache 基金会并成为顶级开源项目。

4.3 Kafka 的特性

(1)高吞吐量、低延迟

Kafka 每秒可以处理几十万条消息,它的延迟最低只有几毫秒。每个 topic 可以分多个 Partition,Consumer Group 对 Partition 进行消费操作,提高负载均衡能力和消费能力。

(2)可扩展性

kafka 集群支持热扩展。

(3)持久性、可靠性

消息被持久化到本地磁盘,并且支持数据备份防止数据丢失。

(4)容错性

允许集群中节点失败(多副本情况下,若副本数量为 n,则允许 n-1 个节点失败)。

(5)高并发

支持数千个客户端同时读写。

4.4 Kafka 系统架构

(1)Broker

一台 kafka 服务器就是一个 broker。一个集群由多个 broker 组成。一个 broker 可以容纳多个 topic。

(2)Topic(主题)

可以理解为一个队列,生产者和消费者面向的都是一个 topic。

类似于数据库的表名或者 ES 的 index。

物理上不同 topic 的消息分开存储。

(3)Partition(分区,实现数据分片)

  • 为了实现扩展性,一个非常大的 topic 可以分布到多个 broker(即服务器)上,一个 topic 可以分割为一个或多个 partition,每个 partition 是一个有序的队列。Kafka 只保证 partition 内的记录是有序的,而不保证 topic 中不同 partition 的顺序。
  • 每个 topic 至少有一个 partition,当生产者产生数据的时候,会根据分配策略选择分区,然后将消息追加到指定的分区的队列末尾。

Partation 数据路由规则:

  1. 指定了 patition,则直接使用;
  2. 未指定 patition 但指定 key(相当于消息中某个属性),通过对 key 的 value 进行 hash 取模,选出一个 patition;
  3. patition 和 key 都未指定,使用轮询选出一个 patition。

注意:

  • 每条消息都会有一个自增的编号,用于标识消息的偏移量,标识顺序从 0 开始。
  • 每个 partition 中的数据使用多个 segment 文件存储。
  • 如果 topic 有多个 partition,消费数据时就不能保证数据的顺序。严格保证消息的消费顺序的场景下(例如商品秒杀、 抢红包),需要将 partition 数目设为 1。

broker、topic、partition三者的关系:

  • broker 存储 topic 的数据。如果某 topic 有 N 个 partition,集群有 N 个 broker,那么每个 broker 存储该 topic 的一个 partition。
  • 如果某 topic 有 N 个 partition,集群有 (N+M) 个 broker,那么其中有 N 个 broker 存储 topic 的一个 partition, 剩下的 M 个 broker 不存储该 topic 的 partition 数据。
  • 如果某 topic 有 N 个 partition,集群中 broker 数目少于 N 个,那么一个 broker 存储该 topic 的一个或多个 partition。在实际生产环境中,尽量避免这种情况的发生,这种情况容易导致 Kafka 集群数据不均衡。

分区的原因:

  • 方便在集群中扩展,每个Partition可以通过调整以适应它所在的机器,而一个topic又可以有多个Partition组成,因此整个集群就可以适应任意大小的数据了;
  • 可以提高并发,因为可以以Partition为单位读写了。

(4)Replication(副本)

副本,为保证集群中的某个节点发生故障时,该节点上的 partition 数据不丢失,且 kafka 仍然能够继续工作,kafka 提供了副本机制,一个 topic 的每个分区都有若干个副本,一个 leader 和若干个 follower。

(5)Leader

每个 partition 有多个副本,其中有且仅有一个作为 Leader,Leader 是当前负责数据的读写的 partition。

(6)Follower

  • Follower 跟随 Leader,所有写请求都通过 Leader 路由,数据变更会广播给所有 Follower,Follower 与 Leader 保持数据同步。Follower 只负责备份,不负责数据的读写。
  • 如果 Leader 故障,则从 Follower 中选举出一个新的 Leader。
  • 当 Follower 挂掉、卡住或者同步太慢,Leader 会把这个 Follower 从 ISR(Leader 维护的一个和 Leader 保持同步的 Follower 集合) 列表中删除,重新创建一个 Follower。

(7)Producer

  • 生产者即数据的发布者,该角色将消息 push 发布到 Kafka 的 topic 中。
  • broker 接收到生产者发送的消息后,broker 将该消息追加到当前用于追加数据的 segment 文件中。
  • 生产者发送的消息,存储到一个 partition 中,生产者也可以指定数据存储的 partition。

(8)Consumer

消费者可以从 broker 中 pull 拉取数据。消费者可以消费多个 topic 中的数据。

(9)Consumer Group(CG)

  • 消费者组,由多个 consumer 组成。
  • 所有的消费者都属于某个消费者组,即消费者组是逻辑上的一个订阅者。可为每个消费者指定组名,若不指定组名则属于默认的组。
  • 将多个消费者集中到一起去处理某一个 Topic 的数据,可以更快的提高数据的消费能力。
  • 消费者组内每个消费者负责消费不同分区的数据,一个分区只能由一个组内消费者消费,防止数据被重复读取。
  • 消费者组之间互不影响。

(10)offset 偏移量

  • 可以唯一的标识一条消息。
  • 偏移量决定读取数据的位置,不会有线程安全的问题,消费者通过偏移量来决定下次读取的消息(即消费位置)。
  • 消息被消费之后,并不被马上删除,这样多个业务就可以重复使用 Kafka 的消息。
  • 某一个业务也可以通过修改偏移量达到重新读取消息的目的,偏移量由用户控制。
  • 消息最终还是会被删除的,默认生命周期为 1 周(7*24小时)。

(11)Zookeeper

  • Kafka 通过 Zookeeper 来存储集群的 meta 信息。
  • 由于 consumer 在消费过程中可能会出现断电宕机等故障,consumer 恢复后,需要从故障前的位置的继续消费,所以 consumer 需要实时记录自己消费到了哪个 offset,以便故障恢复后继续消费。
  • Kafka 0.9 版本之前,consumer 默认将 offset 保存在 Zookeeper 中;从 0.9 版本开始,consumer 默认将 offset 保存在 Kafka 一个内置的 topic 中,该 topic 为 __consumer_offsets。
  • 也就是说,zookeeper的作用就是,生产者push数据到kafka集群,就必须要找到kafka集群的节点在哪里,这些都是通过zookeeper去寻找的。消费者消费哪一条数据,也需要zookeeper的支持,从zookeeper获得offset,offset记录上一次消费的数据消费到哪里,这样就可以接着下一条数据进行消费。

本文为CSDN博主「因为你是在熙啊丶」的原创文章,
原文链接:https://blog.csdn.net/WLDN997/article/details/125606502

作者:聂鲁达的邮差
链接:https://juejin.cn/post/7116213642852302862
来源:稀土掘金

这篇关于消息队列之卡夫卡 + EFLFK集群部署的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

闲置电脑也能活出第二春?鲁大师AiNAS让你动动手指就能轻松部署

对于大多数人而言,在这个“数据爆炸”的时代或多或少都遇到过存储告急的情况,这使得“存储焦虑”不再是个别现象,而将会是随着软件的不断臃肿而越来越普遍的情况。从不少手机厂商都开始将存储上限提升至1TB可以见得,我们似乎正处在互联网信息飞速增长的阶段,对于存储的需求也将会不断扩大。对于苹果用户而言,这一问题愈发严峻,毕竟512GB和1TB版本的iPhone可不是人人都消费得起的,因此成熟的外置存储方案开

服务器集群同步时间手记

1.时间服务器配置(必须root用户) (1)检查ntp是否安装 [root@node1 桌面]# rpm -qa|grep ntpntp-4.2.6p5-10.el6.centos.x86_64fontpackages-filesystem-1.41-1.1.el6.noarchntpdate-4.2.6p5-10.el6.centos.x86_64 (2)修改ntp配置文件 [r

HDFS—集群扩容及缩容

白名单:表示在白名单的主机IP地址可以,用来存储数据。 配置白名单步骤如下: 1)在NameNode节点的/opt/module/hadoop-3.1.4/etc/hadoop目录下分别创建whitelist 和blacklist文件 (1)创建白名单 [lytfly@hadoop102 hadoop]$ vim whitelist 在whitelist中添加如下主机名称,假如集群正常工作的节

Hadoop集群数据均衡之磁盘间数据均衡

生产环境,由于硬盘空间不足,往往需要增加一块硬盘。刚加载的硬盘没有数据时,可以执行磁盘数据均衡命令。(Hadoop3.x新特性) plan后面带的节点的名字必须是已经存在的,并且是需要均衡的节点。 如果节点不存在,会报如下错误: 如果节点只有一个硬盘的话,不会创建均衡计划: (1)生成均衡计划 hdfs diskbalancer -plan hadoop102 (2)执行均衡计划 hd

hdu1180(广搜+优先队列)

此题要求最少到达目标点T的最短时间,所以我选择了广度优先搜索,并且要用到优先队列。 另外此题注意点较多,比如说可以在某个点停留,我wa了好多两次,就是因为忽略了这一点,然后参考了大神的思想,然后经过反复修改才AC的 这是我的代码 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<

阿里开源语音识别SenseVoiceWindows环境部署

SenseVoice介绍 SenseVoice 专注于高精度多语言语音识别、情感辨识和音频事件检测多语言识别: 采用超过 40 万小时数据训练,支持超过 50 种语言,识别效果上优于 Whisper 模型。富文本识别:具备优秀的情感识别,能够在测试数据上达到和超过目前最佳情感识别模型的效果。支持声音事件检测能力,支持音乐、掌声、笑声、哭声、咳嗽、喷嚏等多种常见人机交互事件进行检测。高效推

搭建Kafka+zookeeper集群调度

前言 硬件环境 172.18.0.5        kafkazk1        Kafka+zookeeper                Kafka Broker集群 172.18.0.6        kafkazk2        Kafka+zookeeper                Kafka Broker集群 172.18.0.7        kafkazk3

poj 3190 优先队列+贪心

题意: 有n头牛,分别给他们挤奶的时间。 然后每头牛挤奶的时候都要在一个stall里面,并且每个stall每次只能占用一头牛。 问最少需要多少个stall,并输出每头牛所在的stall。 e.g 样例: INPUT: 51 102 43 65 84 7 OUTPUT: 412324 HINT: Explanation of the s

poj 2431 poj 3253 优先队列的运用

poj 2431: 题意: 一条路起点为0, 终点为l。 卡车初始时在0点,并且有p升油,假设油箱无限大。 给n个加油站,每个加油站距离终点 l 距离为 x[i],可以加的油量为fuel[i]。 问最少加几次油可以到达终点,若不能到达,输出-1。 解析: 《挑战程序设计竞赛》: “在卡车开往终点的途中,只有在加油站才可以加油。但是,如果认为“在到达加油站i时,就获得了一

poj3750约瑟夫环,循环队列

Description 有N个小孩围成一圈,给他们从1开始依次编号,现指定从第W个开始报数,报到第S个时,该小孩出列,然后从下一个小孩开始报数,仍是报到S个出列,如此重复下去,直到所有的小孩都出列(总人数不足S个时将循环报数),求小孩出列的顺序。 Input 第一行输入小孩的人数N(N<=64) 接下来每行输入一个小孩的名字(人名不超过15个字符) 最后一行输入W,S (W < N),用