小田赶牛题解

注:点击标题即可查看原题

NO.1 题意解析

有n头奶牛去小田的花园吃花了,小田需要阻止它们,可是小田每一次只可以牵走一头牛,会耗费t[i]的时间将这头牛牵走,然后又花费同样的t[i]时间返回牧场继续敢牛。每头牛每分钟吃花的速度取决于d[i]。等到小田牵走所有牛时,花已经少了很多。小田如何牵牛使得花被吃掉得更少?

输入描述: 6， 3 1， 2 5， 2 3， 3 2， 4 1， 1 6， 输出描述: 被牛吃掉的最少的花数量 注:为了方便理解,题目有所改动

NO.2 思路解析

这一道题很容易可以看出要先排序,可问题是排序的标准是什么呢?经过分析样例一后可以看出,牛的"危险度"越高,就要越早牵走。 比如说，有两头牛,牛A牵走需要1分钟,每分钟可以吃2朵花,而牛B牵走需要2分钟,但每分钟可以吃1000朵花,这时可以很容易的得出,需要先牵走牛B,因为如果先牵走牛A,等到牵牛B时,牛B已经吃了快2000朵了。所以很显然,牛B的"危险度"是远远大于牛A的。

那么,新的问题又来了,怎么判断牛的危险度和根据危险度排序呢?首先,我们可以联想到,将每一头牛每分钟吃的花的数量进行排序,每分钟吃的花的数量越高,"危险度"自然也随之上升。但是,仔细想就会发现,这样是不对的,因为如果两头牛一头牵走用时1分钟,另一头牵走用时100分钟,两头牛每分钟吃的花数量是相等的,按照刚刚的排序两头牛"危险度"是相等的,可是但凡智力正常的人都会知道,第一头牛(也就是牵走需要1分钟的那一头)危险性是更高的,所以,单独根据每分钟的吃花数量排序是肯定不行的了。既然单独根据吃花量排序不行,那么同理,单独根据牵走用时排序自然也行不通。

此时聪明的你肯定想到了,排序的规则自然是需要结合吃花量和牵走时间,而并不是单独看某一种量。那么,吃花量乘以牵走时间可不可以呢?如果你选了这个那么你就惨了(别问我怎么知道的!),因为吃花量乘以牵走时间只是这一头被牵走的牛在一定时间内吃花的数量,而某一头牛被牵走时已经停止吃草了,那么这个代码求出来的对于这道题目的需求来说就是无意义的。

那么,究竟如何排序牛的"危险性"才正确呢?题目写道,一头牛被牵走时,其它牛仍然在正常吃草。那么,其它牛在这头牛被牵走的时间里的吃草量越高(相对总吃草量),是否意味着这一头牛的危险性越低呢?答案是肯定的,我们不妨想一想我们最开头举的例子,牛A牵走需2分钟,每分钟吃1朵花,牛B牵走需1分钟,每分钟吃1000朵花,此时,如果先牵走牛A的话,剩余的牛(也就是牛B)在牛A被牵走时所吃的草足足有2000朵,而如果先牵走牛B,剩余的牛只吃了1朵花。结果很明显,结论正确,也就是说,一头牛的"危险度"的高低取决于剩余的牛在这一头牛被牵走的时间里(也就是2t[i])的吃草量。

思路正确,这一道题的思路方面也就迎刃而解了。但是,在程序方面仍然会有问题。其中,如何在排序过程中,下标跟着移动成了问题。这个时候就不推荐自己手写排序然后修改过程了,因为对于部分测试点会超时(别问我怎么知道的!)所以可以试着用结构体(注:点击蓝色字体即可打开链接)再用sort排序,好处自然是:快,方便,好使。但是注意了,结构体排序需要再输入一个参数,用于排序规则,这刚好完美的解决了排序的问题。最终,只要依次统计输出,这一道题就解决了。

其实这一道题难度并不是特别难,关键在于逆向思维,能否在做题时不顺从传统思路去想,比如在找排序规则时,其实牛的危险度取决于其他牛而不取决于牛本身。

制作不易,感谢观看,欢迎留言