第一次使用Atcoder官方允許導(dǎo)入的Ruby第三方gem sorted_containers解答此題
E - Library Bookshelf Guide
Time Limit: 2 sec / Memory Limit: 1024 MiB
Score : 433 pts
Problem Statement
Takahashi is working part-time at a library. The library has a bookshelf with N storage spaces arranged in a single row from left to right, and each storage space can hold one book. The storage spaces are numbered 1,2,…,N from left to right. Initially, all storage spaces are empty.
Today, Takahashi is in charge of placing M newly arrived books on the bookshelf. The storage space number where each book should be placed is predetermined: the book with placement order i (1≤i≤M) is placed in storage space Si . No two books are placed in the same storage space. That is, S1,S2,…,SM are all distinct values. Takahashi places the books one by one on the bookshelf in the order of the 1st book, the 2nd book, …, the M-th book.
To make the task more efficient, Takahashi wants to know in advance, when placing each book, "among the storage spaces that are currently empty at that moment, what is the position from the left of the storage space where this book should be placed?"
Specifically, just before placing the i-th book, if we number the currently empty storage spaces
1,2,… from left to right, storage space Si is the Pi -th from the left. Find Pi for each i=1,2,…,M.
Constraints
1≤M≤N≤2×10**5
1≤Si ≤N
All Si are distinct
All input values are integers
Input
N M
S1 S2…SM
The first line contains an integer N representing the total number of storage spaces and an integer M representing the number of books to be placed, separated by a space.
The second line contains the storage space numbers S1,S2,…,SM where each book should be placed, separated by spaces.Si represents the storage space number for the book with placement order i.
Output
P1
P2
?
PM
Output M lines.On the i-th line, output an integer Pi representing the position of storage space Si when counting the empty storage spaces from left to right just before placing the i-th book.
我的解
require "sorted_containers"
n, m = gets.split.map(&:to_i)
s = gets.split.map(&:to_i)
list = SortedContainers::SortedArray.new
(1..n).each do |x|
list << x
end
s.each do |y|
pos = list.bisect_left(y)
puts pos + 1
z = list[pos]
list.delete(z)
end
