Cho một mảng danh sách chiều cao và số lượng người có chiều cao lớn hơn. Hãy tìm ra vị trí chính xác của mỗi người
Người có chiều cao 33 không có ai cao hơn đứng trước, người 11 có 2 người cao hơn đứng trước ...
Giải thuật: Sắp xếp lại mảng, điền dần vị trí của người có chiều cao thấp nhất đến người có chiều cao cao nhất.
Sau khi sắp xếp ta được mảng chiều cao a[1, n] với người có chiều cao a[i] sẽ có x người đứng trước. x chính là số vị trí trống phía trước khi xếp người a[i]
Sau khi sắp xếp ta có mảng sau. 11 22 33 44 55 tương ứng có dãy số người đứng trước như sau 2 1 0 1 0
điền 11 sao cho có 2 ô trống phía trước do đó 11 sẽ ở ô a[2], 22 có 11 người đứng trước sẽ ở ô a[1], và 33 ở ô a[0], sau đó 44 sẽ ở ô a[5] để đảm bảo trước nó có 1 ô trống.
Giải thuật: Sắp xếp lại mảng, điền dần vị trí của người có chiều cao thấp nhất đến người có chiều cao cao nhất.
Sau khi sắp xếp ta được mảng chiều cao a[1, n] với người có chiều cao a[i] sẽ có x người đứng trước. x chính là số vị trí trống phía trước khi xếp người a[i]
Sau khi sắp xếp ta có mảng sau. 11 22 33 44 55 tương ứng có dãy số người đứng trước như sau 2 1 0 1 0
điền 11 sao cho có 2 ô trống phía trước do đó 11 sẽ ở ô a[2], 22 có 11 người đứng trước sẽ ở ô a[1], và 33 ở ô a[0], sau đó 44 sẽ ở ô a[5] để đảm bảo trước nó có 1 ô trống.
Solution