//
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


[]

Advertisements

About pascalteacher

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

Thảo luận

Không có bình luận

Trả lờ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 Đăng xuất / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Đăng xuất / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Đăng xuất / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Đăng xuất / Thay đổi )

Connecting to %s

Các tác giả

Categories

Tháng Mười Hai 2016
H B T N S B C
« Th11   Th1 »
 1234
567891011
12131415161718
19202122232425
262728293031  

NCT Computer

Flickr Photos

Thống kê

  • 150,179 lượt xem

pascalteacher.nct@gmail.com


Trang huấn luyện học sinh giỏi Tin học

%d bloggers like this: