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
Bạn phải đăng nhập để gửi phản hồi.
a[i][0]
x có thể âm