youmu. Yuyuko and Youmu

youmu. Yuyuko and Youmu

ZOJ3384. 幽幽子与妖梦

downloadsource code (ZOJ3384.cpp) [贪心(greedy)]

这是我在凌晨两三点的时候,为题目不足的Contest 8 by ACFun临时补的一道超水的签名题,当时在20min内的10个提交都是1y。题目捏的自然是有幻想乡第一大胃王之称UU子,还有「みょん」(“Myon”)也是来自东方妖妖梦Extra的neta。附上几篇「メイドさんの日々」,类似的四格还有很多。

p19 p24 p34 p35
p82 p83 p84 p85

  • 幽冥楼閣の亡霊少女/華胥の亡霊/西行寺幽々子(さいぎょうじ ゆゆこ)
  • 幽人の庭師/半分幻の庭師/半人半霊の半人前/魂魄妖夢(こんぱく ようむ)

在连续N天里,妖梦在第i天可以准备ai的食物,而UU子则要吃掉bii的食物,第一天并没有食物剩余,要为妖梦提供方案,使得她能够为UU大人提供足够且尽量新鲜的食物。如果不存在满足条件的方案,那么输出”Myon”。

算法是O(n)的,不过O(n^2)也能过,也确实有人用了O(n^2)的方法。因为题目要求食物尽量新鲜,所以只要从后往前扫,在第i天,首先让UU大人吃上当天制作的食物,如果食物不足,那么只能在前几天多准备一些了,假设还差c的食物,事实上就可以当作UU子在第i-1天需要吃ai-1+c的食物来做。如果第一天的食物依然不足,就输出”Myon”。





©2010 Zhejiang University ACM/ICPC Team
©2010 http://watashi.ws/acm_x_touhou/

Leave a Reply