Số lượng submit của website có hạn, rất mong các bạn chau chuốt thật kỹ code trước khi submit! Ủng hộ 20.000 (hai mươi ngàn đồng) để chúng tôi duy trì website.

Biến đổi dãy 2

Đề bài: Sơn có một ma trận a được thiết lập như sau:

a[i].size()=2. (0 ≤ i < a.size()).
a[i][0] ≤ a[i][1].
Một lần biến đổi Sơn thực hiện các việc như sau:

Tăng tất cả a[i][0] lên x đơn vị cho đến khi tồn tại a[i][0]=a[i][1]
Xóa tất cả các phần tử mà a[i][0] = a[i][1]
Sơn muốn biết phải biến đổi bao nhiêu lần để a không còn phần tử nào.
Với a = [[1,2],[3,5],[2,4],[5,6]] thì kết quả = 2.
Giải thích:
Lần biến đổ thứ 1:
Tăng tất cả a[i][0] lên 1 đơn vị cho đến khi tồn tại a[i][0]=a[i][1], a = [[2,2],[4,5],[3,4],[6,6]]
Xóa a[0] và a[3], a = [[4,5],[3,4]]
Lần biến đổi thứ 2:
Tăng tất cả a[i][0] lên 1 đơn vị cho đến khi tồn tại a[i][0]=a[i][1], a = [[5,5],[4,4]
xóa a[0] và a[1], lúc đó a rỗng và kết thúc.
Với a = [[1,2],[2,3],[3,4]] thì kết quả = 1.
Đầu vào: Một số n là kích thước của mảng, một mảng 2 chiều kích thước n*2
Đầu ra: Số lần biến đổi để a không còn phần tử nào.
Chương trình mong muốn: O(nlogn)

Ví dụ:

input:
4
1 2
3 5
2 4
5 6
output:
2
input:
3
1 2
2 3
3 4
output:
1

Bạn chưa đăng nhập? Đăng nhập để Submit ngay!

Add a Comment