P1420: 【试题7】大鱼吃小鱼

---

题目描述

【试题7】大鱼吃小鱼
小黄发现他的鱼缸里的观赏鱼越来越少了。仔细观察才发现，即使按时喂鱼，一些大鱼也会争着吃小鱼——但是不会吃比它小太多的鱼。准确地讲，若一条大小是a的鱼，当存在另外一条鱼（大小是b）个头比它小，但两条鱼个头的差不超过整数k时（即a-b≤k），a会吃掉b。吃掉后，a不会变大，b会消失。
如：当所有鱼的大小是a=[101，53，42，102，101，55，54]且k=1时，一种可能的掠食过程是(下划线表示被吃)：[101，53，42，102，101，55，54]→[101,53，42，102,55,54]→[101,42，102，55，54]→[42，102，55，54]→[42，102,55]，最后只剩下3条鱼。现在请编写程序模拟研究一下，对于给定的鱼大小和k的值，最坏情况下会剩几条鱼。
【输入】
三行，第一行是鱼的条数，第二行是所有鱼的大小，第三行是k值（鱼的数量最多50条，鱼的大小为10～500之间的整数）。
【输出】
最坏情况下剩下鱼的数量。
【输入样例】
    7
101  53  42  102  101  55  54
1
【输出样例】
3

来源

 

问题信息

时间限制 1.000s
内存限制 128MB
评测方式 Normal Judge

咻咻~

提交 状态