这个做法很显然是错误的吧
by Sora1336 @ 2022-10-20 07:29:10
因为时间复杂度是假的
by Sora1336 @ 2022-10-20 07:31:24
你要去找一个区间内的最开始有石头的点的话,一个区间一个区间的跳时间复杂度就已经是 $O(nk)$ 了
by Sora1336 @ 2022-10-20 07:33:02
@[MHYC133](/user/613066)
而且也有反例
```
10
4 6 4
2 6 7 9
```
根据你的做法,第一步会跳到 5。然后第二步就只能跳到 9,因为最小跳 4 个。踩到一个石子。
但是实际上应该先跳到 4 再到 8 再跳出去。踩到 0 个。贪心就寄了。
by Sora1336 @ 2022-10-20 07:44:01
00010011010
s=4,t=6
用a表示所在位置的话:
a0010011010
0001a011010
00010011a10
所以就是跳不到终点是吗 =.=
by MHYC133 @ 2022-10-20 19:22:47
不是我怎么感觉我的贪心没问题呢
:/
by MHYC133 @ 2022-10-20 20:47:16
因为我是找第一个空地跳啊
(先不管复杂度,总有办法优化)
所以我会先跳4再到8再出去啊
by MHYC133 @ 2022-10-20 20:49:03
@[Sora1336](/user/294745)
你这反例有问题啊 :/
by MHYC133 @ 2022-10-21 20:17:54
@[MHYC133](/user/613066) 你找第一个空地跳那更是 naive
by Sora1336 @ 2022-10-22 08:06:26
@[MHYC133](/user/613066)
反例如下:
s=4 t=6
石头:
00011100001110101110
你的算法会这么做:
a0011100001110101110
000111a0001110101110
000111000011a0101110
000111000011101011a0
踩到2个石头
而正确的应该是:
a0011100001110101110
00011a00001110101110
000111000a1110101110
0001110000111a101110
0001110000111010111a
踩到1个
by CoderXL @ 2022-10-27 15:06:43