主题:第75次编程比赛结果
我感觉这次比赛出得很烂,人烂题目更烂,才导致参加的人这么少。
我就先说下出这道题目的过程中的一些想法,明天在宣布由谁来主持下场比赛。
题目最先的原型来自一道叫做dota651里面补刀的一道题目,就是根据一些数据,求出能补刀补上的时机,该题目我想到的解法是2分,但是代码写上之后提交,果然WA了。
我就打算出个2分的题目,这道题的最先版本是没有周期和下限的。我一想,太简单了。于是把周期之类啥的能加的都加上,尽量让它看上去很牛逼,当时也没有细想,粗略的想了一下nlogn应该能出结果吧,所以最先的数据量是50万,汗。
后来我又仔细的想了很久,但是终于我败了...想来想去只有暴力才是王道。
忽然发现某o(N)算法其实是错的。。。。期待版主把她的o(N)算法写出来。
说到枚举,我想到一个比现在这个稍微好点的方法。。。就是不用每个时间点去试探,只是需要减少的时候才去减,时间复杂度可以降到O(T*log(n)),T = sum((Ai-Di)/Ci),如果Ci为1,而差平均为K,那么复杂度就是O(K*n*log(n))。
下次比赛就由mht@来主持吧,我再给你加了点,你分最多,我相信你。
我就先说下出这道题目的过程中的一些想法,明天在宣布由谁来主持下场比赛。
题目最先的原型来自一道叫做dota651里面补刀的一道题目,就是根据一些数据,求出能补刀补上的时机,该题目我想到的解法是2分,但是代码写上之后提交,果然WA了。
我就打算出个2分的题目,这道题的最先版本是没有周期和下限的。我一想,太简单了。于是把周期之类啥的能加的都加上,尽量让它看上去很牛逼,当时也没有细想,粗略的想了一下nlogn应该能出结果吧,所以最先的数据量是50万,汗。
后来我又仔细的想了很久,但是终于我败了...想来想去只有暴力才是王道。
忽然发现某o(N)算法其实是错的。。。。期待版主把她的o(N)算法写出来。
说到枚举,我想到一个比现在这个稍微好点的方法。。。就是不用每个时间点去试探,只是需要减少的时候才去减,时间复杂度可以降到O(T*log(n)),T = sum((Ai-Di)/Ci),如果Ci为1,而差平均为K,那么复杂度就是O(K*n*log(n))。
下次比赛就由mht@来主持吧,我再给你加了点,你分最多,我相信你。

您所在位置:

