//
you're reading...
Bài tập huấn luyện

Bài tập huấn luyện: Sắp xếp

Có N viên bi màu được sắp thành một hàng trên mặt đất, các viên bi thuộc 1 trong K màu được đánh số từ 1 đến K.

Để tiện phân loại, beo_chay_so muốn sắp xếp lại các viên bi này sao cho các viên bi cùng màu thì nằm cạnh nhau, như vậy beo_chay_so sẽ thu được các đoạn liên tiếp gồm những viên bi cùng màu, mỗi màu chỉ thuộc đúng 1 đoạn.

Mỗi lần beo_chay_so chỉ được đổi chỗ 2 viên bi cạnh nhau, hãy giúp beo_chay_so sắp xếp lại các viên bi này sao cho số lần phải đổi chỗ các viên bi là ít nhất.

InputSORT.INP

  • Dòng thứ nhất ghi 2 số N và K là số viên bi và số màu.
  • Dòng thứ hai ghi N số nguyên dương là màu của N viên bi theo thứ tự.

Output:            SORT.OUT

Ghi ra duy nhất một số nguyên là số phép đổi chỗ ít nhất.

Giới hạn:

  • 2 ≤ N ≤ 20000.
  • 1 ≤ K ≤ 10
  • Thời gian: 2 s/test
  • Bộ nhớ: 2 MB

Ví dụ:

SORT.INP SORT.OUT Giải thích
8 3

1 1 2 1 2 3 2 3

2 Đổi chỗ số thứ 3 và 4:

1 1 1 2 2 3 2 3

Đổi chỗ số thứ 6 và 7:

1 1 1 2 2 2 3 3

     
SORT.INP SORT.OUT Giải thích
5 3

3 2 1 3 2

3 Đổi chỗ số thứ 3 và 4:

3 2 3 1 2

Đổi chỗ số thứ 4 và 5:

3 2 3 2 1

Đổi chỗ số thứ 2 và 3:

3 3 2 2 1

About pascalteacher

Trang thông tin Toán học và Tin học

Thảo luận

Chưa có phản hồi.

Gửi phản hồi

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s

Các tác giả

Tháng Mười 2016
M T W T F S S
« Sep   Nov »
 12
3456789
10111213141516
17181920212223
24252627282930
31  

NCT Computer

Flickr Photos

A bellezza di a natura (C☺rsica)

Southern White-faced Owl D75_5752.jpg

2016 Lake Yamanaka winter Fuji

More Photos

Thống kê

  • 78,768 lượt xem

%d bloggers like this: