trang chủ / đề bài / icpc20_reg_g

Hoán vị tuyệt vời nhất

Đề bài

Mô tả

Một hoán vị n phần tử là một cách sắp xếp lại n số nguyên dương đầu tiên. Ví dụ, với n=3 có 6 hoán vị: (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2) và (3,2,1). Một hoán vị tuyệt vời là một hoán vị n phần tử có dạng i,i+1,i+2,…,n,1,2,…,i−1. Nói cách khác, hoán vị tuyệt vời thu được bằng cách chuyển một tiền tố của 1,2,…,n sang bên phải. Lưu ý rằng 1,2,…,n cũng là một hoán vị tuyệt vời.

Với một hoán vị, định nghĩa trọng số của nó là số lần ít nhất cần đổi chỗ hai phần tử kề nhau để hoán vị trở thành một hoán vị tuyệt vời.

Ví dụ, trọng số của 3,2,1,4 là 2, vì có thể biến nó thành hoán vị tuyệt vời sau ít nhất hai lần đổi chỗ:

  • Đổi chỗ phần tử thứ 1 và thứ 2: 2,3,1,4.
  • Đổi chỗ phần tử thứ 3 và thứ 4: 2,3,4,1.

Cho một dãy biểu diễn một hoán vị bị mất một số phần tử. Hãy tính trọng số nhỏ nhất trong số tất cả các hoán vị có thể thu được bằng cách thay các phần tử bị mất bằng những giá trị phù hợp. Ví dụ, với dãy 2,3,0,0, trong đó các số 0 là phần tử bị mất, có hai hoán vị có thể là 2,3,1,4 với trọng số 1 và 2,3,4,1 với trọng số 0. Vậy trọng số nhỏ nhất là 0.

Dữ liệu vào

  • Dòng đầu tiên chứa số nguyên t: số bộ dữ liệu.
  • Mỗi bộ dữ liệu gồm:
    • Dòng thứ nhất chứa số nguyên n: số phần tử của hoán vị.
    • Dòng thứ hai chứa n số nguyên a1,a2,…,an cách nhau bởi dấu cách. Dữ liệu đảm bảo luôn thu được ít nhất một hoán vị hợp lệ sau khi thay tất cả các số 0 bằng các giá trị khác.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra kết quả trên một dòng.

Ràng buộc

  • 1≤n≤106.
  • 0≤ai≤n.
  • Tổng n của tất cả các bộ dữ liệu không vượt quá 106.

Ví dụ

Input Output Giải thích
2
4
3 2 1 4
4
2 3 0 0
2
0
Hai bộ dữ liệu chính là hai ví dụ trong đề bài.
5
1
1
1
0
3
0 0 0
5
5 4 3 2 1
5
0 1 0 0 2
0
0
0
4
2
Với 5,4,3,2,1, hoán vị tuyệt vời gần nhất là 3,4,5,1,2 (hoặc 4,5,1,2,3), cần 4 lần đổi chỗ. Với bộ cuối, điền thành 3,1,4,5,2 rồi đưa về 3,4,5,1,2 bằng 2 lần đổi chỗ.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0