Hack
查看原帖
Hack
114502
little_brush楼主2022/9/7 08:07

Hack数据如下:

6
1 1
1 2
2 1 
2 2
2 3
2 4

官方题解中给出的代码输出:

2
1 3 
0 1
3

而正确的输出应该为:

3
1 3 5
0 1
1

原因在于题目说保证数据有解,但是并不保证对于任意一组求出来的(x,z)都有解,所以题解在求出 x=( 0 , 1 ) , z=3 之后并没有检验是否合法,而是直接用于更新答案。

但是如果对于每一种方案都检验是否合法的话,复杂度可能又会退回到 O(n2)O(n^2) 的级别,不知道有没有办法优化。

2022/9/7 08:07
加载中...