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)O(n2) 的级别,不知道有没有办法优化。