Oj.Nbdp.Net
初赛题库
问题
状态
排名
团队
题解
课程
Login
问题 2683 --P1083 分糖果
2683: P1083 分糖果
警告!
题目
状态
题解
题目描述
童年的我们,将和朋友分享美好的事物作为自己的快乐。这天,C小朋友得到了Plenty of candies,将要把这些糖果分给要好的朋友们。已知糖果从一个人传给另一个人需要1 秒的时间,同一个小朋友不会重复接受糖果。由于糖果足够多,如果某时刻某小朋友接受了糖果,他会将糖果分成若干份,分给那些在他身旁且还没有得到糖果的小朋友们,而且自己会吃一些糖果。由于嘴馋,小朋友们等不及将糖果发完,会在得到糖果后边吃边发。每个小朋友从接受糖果到吃完糖果需要m秒的时间。那么,如果第一秒C小朋友开始发糖,第多少秒所有小朋友都吃完了糖呢?
输入
第一行为三个数n、p、c,为小朋友数、关系数和C小朋友的编号。第二行为一个数m,表示小朋友吃糖的时间。下面p行每行两个整数,表示某两个小朋友在彼此身旁
输出
一个数,为所有小朋友都吃完了糖的时间
样例输入输出
输入#1
复制
4 3 1 2 1 2 2 3 1 4
输出#1
复制
5
提示
【限制】 40%的数据满足:1< =n< =100 60%的数据满足:1< =n< =1000 100%的数据满足:1< =n< =100000 m< =n*(n-1)/2,不会有同一个关系被描述多次的情况。 【样例解释】 第一秒,糖在1手上。第二秒,糖传到了2、4的手中。第三秒,糖传到了4的手中,此时1吃完了。第四秒,2、3吃完了。第五秒,4吃完了。所以答案是5。
发表题解
序号
标题
作者
发表时间
费用
订购数
操作
题目信息
提交
难度
普及/提高-
标签
点击显示
if ($pr_flag) { ?>
递交数
4
已通过
3
} ;?>
通过率
75%
时间限制
1 秒
内存限制
128 MB
来源
tyvj
收藏
标签云
模拟
数学与数论
动态规划
贪心
字符串
排序
枚举
数组与串
深搜
高精度
循环结构
递推
递归
二分三分
宽搜
背包
质数
线段树
分治
N进制
图论
队列
最短路
堆
树
并查集
栈
状态压缩
分支结构
几何
博弈论
生成树
顺序结构
离散化
hash表
位运算
单调队列
树状数组
KMP
字典树
二分图
数学期望
AC自动机
树链剖分
差分约束
数位动态规划
函数与过程
网络流
单调栈
前缀和