NOIp模拟题 之 肮脏的牧师 （桶排序）

闲话：

考场上看到了这一题，简直令我震惊！啊！居然还有真么简单的模拟题！良心啊！

而且，还是我 痴迷的 熟悉的游戏 ——  欧气传说 炉石传说！

（话说题面的那三张卡都贼 恶心 好用！都可以在前期打出非常不错的控场与压制！）

然而……说来惭愧……结果我又一次没有A掉这道水题……60分滚粗……（爆点十分诡异而离散，大概是没有注意到一些细节吧）

作为一名 肮脏的 资深的牧师玩家，这简直丢脸丢到家了……

想当年我克苏恩脏牧套牌上场战吼40+伤爆对面脸，心火牧死亡领主平A一下32伤，还有……

啊啊啊啊啊！！！然而我竟然还是没有码出这一题！！！

于是我立志今天晚上绝不玩牧师！！！（貌似暴露了一些什么）……

虽然今晚不玩，但我还是要膜一波——

心火牧万岁！核弹牧万岁！龙牧万岁！宇宙牧万岁！亡语牧万岁！偶数牧万岁！野猪牧万岁！

安度因万岁！泰兰德万岁！圣光万岁！

（另外：圣光说，我这次NOIp能考420+哦！嘻嘻嘻……沉浸梦幻无法自拔……）

题面（经过文艺的博主精心优化）：

在炉石传说中脏牧有一张一费的法术疯狂药水，效果是将一个攻击力不超过2的随从“拉过来”（就是变成你的随从）

同时脏牧还有一张更脏的四费的法术暗影狂乱，效果是将一个攻击力不超过3的随从“拉过来”（同上）

然后脏牧还有一张最最最最脏的法术缩小药水，效果是将敌方所有随从攻击力减少3，而且只消耗一点费用！！！

由于爬虫之王ZMY已经帮你写好了一个叫做紫色岩虫的外挂，炉石官方的系统崩溃了。

这意味着你的手牌没有上限，而且同名卡牌可以无限携带（本来只能带两张）！

然而你的旗鼓相当的对手“自信玩家ZMY”也让自己卡出了一个名叫硬壳甲虫的BUG，这意味着他可以出战无限随从。

于是你们不妨来一场单挑，因为神仙打架的游戏仍然是公平的。

不过资深的老玩家PCY早已发觉，其实你的卡组克制ZMY。

所以你可以用这套脏牧套卡再教育一次ZMY了（是不是很开心）。

不过，既然是教育，当然是当你被对面压场后一回合翻盘直接爆脸才有效果啦！

于是为了准备这场“公平”对决，你已经叫来了卡扎库斯来帮你配置药水。

众所周知，缩小药水的重要原料之一是JYH巨佬的女装照片

可是缩小药水实在太变态了。为了维持对局公平，JYH已经停止向你供应照片。

而且 终结者 管理员HZW已经离机房不远了，所以你不得不快速炼好药水。

所以你不得不找他的好朋友LXT来讨照片。

这显然是非常麻烦而费力的操作。

于是你希望尽量使用较少的缩小药水爆ZMY的脸。

同时，如果在满足使用最少的缩小药水的情况下，你当然希望尽量少的花费法力水晶，（因为法力水晶实在是太可爱了）

这样的话，你很有必要计划一套方案——

你已经得到了这些信息：

ZMY手上有n个随从，它们的攻击力分为k[i]点（1<=i<=n）;

ZMY的 脸 英雄还剩下m点血量。

你需要输出：当在上述所言的最优方案时，

你要配置多少缩小药水，花费多少法力水晶？

如果你一回合不能成功爆他脸，你其实会被他一波反扑而搞死。

所以，当你发现你无论如何都无法取胜时，你会拍案站起，然后大声素质一波——

即输出“Human Cannot Win Dog!!!”（不含引号）

输入格式：

第一行两个整数分别代表n, m；

第二行n个整数。其中第i个整数代表k[i]随从的攻击力。

输出格式：

只有一行两个整数u, v；

分别代表你最少需要配置多少瓶缩小药水已经在保证缩小药水用量最少的情况下你最少要花费多少法力水晶（费用）；

或者是一行一句素质的话（你懂的）。

样例输入：

3 5

1 2 3

样例输出：

0 5

数据范围：

0 <= n, m <= 5000000;

0 <= k[i] <=30000;

分析&题解:

非常显然，那么多个数（5e6），那么点儿范围（3e4）；

不用桶序用什么？

然后貌似就都非常显然了。

随便贪一贪，就可以A掉了。

也许很多同学还没有接触过桶排序，

那不妨让博主来给大家介绍一下桶排序吧。

桶排序，顾名思义，就是把东西放到桶子里去，再取出来，就变得有序了。

这是什么意思呢？

打个比方，你有大把大把散乱的钞票，你当然要帮他们按金额排好序。

然而怎么做到呢？

很简单， 我们只需要预先建好一个桶（数组），

下标代表每一个可能金额。

每来一个钞票（元素），

就把它丢到那个桶子去（相应下标的数组值加一），

最后按照桶内钞票种类金额从小到大，一桶一桶“倒出来”，

不就变得有序了吗？

代码实现非常简单，这里就不加以赘述了。

那么，这题貌似就是这样了。

嗯。话不多说，附上代码吧！

（苯宝宝的这台电脑貌似不支持复制操作…那只好，回头再补了…）

转载于:https://www.cnblogs.com/charlotte-Y/p/9877340.html