Hướng dẫn cho Bedan Contest #05 - F - Đảo ngược

Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.

Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.

Authors: flo

Cách giải

Hint

Với mỗi $i$ thỏa mãn $1 \le i \le n$ , ta sẽ tìm cách để đảo ngược sao cho $a_i = b_i$ . Khi đó thì tại mỗi vị trí $i$ , các phần tử từ $1$ đến $i-1$ rõ ràng đã thỏa mãn đề bài.

Solution

Từ nhận xét trên, với mỗi vị trí $i$ thỏa mãn $1 \le i \le n$ , ta sẽ tìm vị trí $j$ thỏa mãn $a_j = b_i$ $(i \le j \le n)$ và đảo ngược đoạn $[i, j]$ của dãy $a$ . Khi đó, $a_i = a_j$ và $a_j = b_i$ nên $a_i = b_i$ . Bởi thao tác này chỉ được áp dụng tối đa $1$ lần lên các phần tử nên tổng số thao tác sẽ không vượt quá $n$ .
Độ phức tạp của ý tưởng trên là $O(n^2)$ , việc đảo ngược đoạn con cũng tốn độ phức tạp là $O(n)$ nhé.
Sự thật là bài này mình lấy ý tưởng từ bài CSES - Reversal Sorting nên đừng thắc mắc tại sao nó lại khá giống nhau.

Bình luận

Không có bình luận nào.