24OJ #33. 【2017省选模拟】物品 贪心

考场上写了个nlogn^2的算法,感觉本机只能40。QAQ 3 * 10^4都过不去,然后忽然发现自己水到70分。貌似评测机比较快,然后数据有点水,然后貌似可能大数据对于cpu的缓存机制稍快一点。

考试的时候写的二分时间答案,然后nlogn暴力判断能否可行,一个物品自己涨够就认为其多余的时间在分裂。这样子时间不太优美。。。

我们考虑一下,每次我们时间+1,无非就是以下情况。

1 2 3 4 5

0 1 2 3 4

0 0 1 2 3

0 0 1  2

0 0 1

0 0

0

我们发现除了初始状态,其余共6层,符合样例。

大量数据证明这么做没什么问题。。。。。。。

我们照着模拟就行了。

 

“24OJ #33. 【2017省选模拟】物品 贪心”的2个回复

发表评论