‘哦’一下,岂不是显得我很笨?”
“…………有道理!哦!!”
“???”
蒋嘉齐不以为意,道:“陈舟的思路,跟我的思路一模一样。”
李崖问:“那你倒是说说,怎么证明它一定是连续的区间?”
蒋嘉齐尴尬了,“呃,这个嘛……”
蒋嘉齐心想,我知道个屁啊!我要是知道,站在讲台上的人就是我了!
老子就是卡在这一步!
这时,罗季瑶站起来问道:“陈舟,你说的这个关键性质,要如何证明呢?”
陈舟道:“这个很简单,我们用反证法即可。”
“显而易见!有解时,最后一行要么是连续区间,要么就存在中间有断点的情况,没有第三种可能。”
“那么我们假设,某个蓄水厂复盖的最后一行的城市不连续,中间有断点。”
“那么,由于水只能从高往低流,这个断点城市的海拔必须比左右两边都高,也比它上面的城市高,导致水无法从任何方向流到它,这就与‘有解’矛盾。”
这下,台下约莫四分之一的同学,不约而同地“哦”了一声。
蒋嘉齐、李崖、罗季瑶和曾蝶,更是点了点头,异口同声道:“我知道该怎么做了!”
蒋嘉齐懊悔得肠子都青了,“妈的!我把它抽象成一个数学模型,就是没想到它还是一个地理题!”
李崖叹了口气,“俺也一样。”
三个女人一台戏这边,黄玲懵圈,“不是,曾蝶,你也知道了?”
曾蝶微微一笑,“剩下的步骤不是显而易见吗?傻瓜都能看出来。”
“傻瓜?”
黄玲呆了呆,质问道:“说谁呢?是不是在说我?”
曾蝶连忙摆手,“不是不是,我不是针对你。”
黄玲:“??”
什么叫不是‘针对’我?那不还是说我是傻瓜吗?
罗季瑶坐下道:“有了陈舟刚刚提到的关键性质,问题确实简单多了。”
黄玲问:“不是!究竟哪里简单了?”
罗季瑶道:“因为后面只需要对第一行的每个城市,计算它能复盖的最后一行的区间[left, right]。”
曾蝶接话道:“对!,用最少的区间复盖[1, ]这个范围。”
罗季瑶点点头,“到了这个时候,就变成了一个非常典型的‘贪心算法问题’。”
“???”
黄玲彻底懵圈,“不是,合著你俩都是大佬,就我一个菜鸡?”
曾蝶笑而不语。
罗季瑶安慰道:“其实我也是菜鸡,真正的大佬是陈舟。”
此刻,台上的陈舟讲解完毕,道:“所以,我们可以看出,这道题考察了图论搜索、性质证明和贪心算法的综合运用。”
“重中之重,其实还是得发现‘连续区间’的性质,并将问题转化为区间复盖问题。”
“好了,就是这样。”
说完,陈舟将手中的粉笔丢到了讲台桌上,拍了拍满是粉笔灰的手。
陆海峰教授带头鼓掌,满眼都是爱才之情,“好!”
然后,裴朱在心中暗道了一声“这小子牛啊”,旋即也鼓起掌来。
紧接着,全场所有同学都为陈舟鼓掌喝彩!
“啪啪啪啪!”
一时间掌声雷动!
许久之后,这如海潮般的掌声方才逐渐退去。
讲台上,裴朱教授上前拍了拍陈舟的肩膀,目光之中满是欣赏之色。
裴朱道:“陈舟,你小子是个人才啊!”
“这么多年来,第一次有人能在这么短的时间内,解开我抛出来的难题。”
“不错不错,继续努力!”
陈舟笑了笑,摊开手,“裴教授,您不是说,有人做出来了,有500块的彩头吗?”
裴朱:“呃…………”
有同学在台下起哄道:“裴教授,您不会是想耍赖不给吧?”
裴朱道:“我怎么可能耍赖?我这是忘带钱了。”
陆海峰教授摸出钱包,“没事,我带了,下次记得还钱哈。”
见状,台下顿时哄堂大笑。
李崖幸灾乐祸道:“蒋嘉齐,这下你也体会到被人碾压的感觉了吧?”
闻言,蒋嘉齐没好气地“嘿”了一声,回过头,一脸不服气。
蒋嘉齐道:“哪里碾压了?我跟他差不多,无非是我慢了一点点而已,多给我十五分钟,我也一样能做出来了!”
“要不让他换个题再比一比,指不定谁更快!”
李崖“呵”了一声,“死鸭子嘴硬。”
蒋嘉齐:“你!!”
李崖又补刀道:“再说了,就算再给你十五分钟,二十五分钟,你能跟陈舟一样,想出三种解法吗?”
蒋嘉齐“嘁”了一声,不以为意,“他说什么,你就信什么?能不能有点独立思考的能力?”
“涨别人威风,灭自己志气!好歹你我都是四七九的学生,他陈舟一个棠中的,再牛逼,又能比我们牛到哪