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

Bài tập huấn luyện: Xếp hàng

[Bộ đề huấn luyện vòng tỉnh Đồng Tháp]


Chọn đội tuyển dự thi quốc gia – 2016 – Ngày thi 17/5/2015 – Bài 3


Đề bài


Trong buổi lễ tổng kết năm học, có N học sinh được xếp thành một hàng. Cách xếp hàng của các học sinh chưa được đẹp mắt nên ban tổ chức xếp lại hàng theo chiều cao không giảm. Cách xếp hàng của ban tổ chức như sau: di chuyển một học sinh bất kỳ về đầu hàng hoặc cuối hàng cho đến khi được một hàng có chiều cao không giảm.

Yêu cầu: Bạn hãy giúp ban tổ chức xếp hàng sao cho số lần di chuyển học sinh là ít nhất.

– Dữ liệu vào: Cho từ tệp văn bản XEPHANG.INP có cấu trúc:

  • Dòng thứ nhất ghi số nguyên dương N là số học sinh (1 < N ≤ 105).
  • Dòng thứ hai ghi N số nguyên dương H1, H2, …Hn là chiều cao của N học sinh đang xếp hàng (1 ≤ Hi ≤ 109; i=1..N).

Các số trên một dòng được ghi cách nhau bởi kí tự trắng

– Kết quả: Ghi vào tệp văn bản XEPHANG.OUT có một số nguyên dương duy nhất là số lần di chuyển học sinh ít nhât.


– Ví dụ :

XEPHANG.INP XEPHANG.OUT Giải thích
4

2 1 3 5

1 Di chuyển học sinh chiều cao 1 về đầu hàng: 1 2 3 5
3

3 2 1

2

 

Di chuyển học sinh chiều cao 1 về đầu hàng:  1 3 2

Di chuyển học sinh chiều cao 3 về cuối hàng: 1 2 3 

5

3 7 2 6 9

3 3 2 6 9 7

2 3 6 9 7

2 3 6 7 9

Hạn chế kĩ thuật:

+ Có 70% số test tương ứng 70% số điểm có N ≤ 103

+ Có 30% số test tương ứng 30% số điểm có 103 < N ≤ 105


Hướng dẫn


[]


Chương trình


[]

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ả

Danh mục

Tháng Mười Hai 2016
M T W T F S S
« Nov   Jan »
 1234
567891011
12131415161718
19202122232425
262728293031  

NCT Computer

Flickr Photos

sunset

Detroit Night

White-winged Scoter | Macreuse à ailes blanches

More Photos

Thống kê

  • 95,281 lượt xem

%d bloggers like this: