WEBSITE ĐÃ HOẠT ĐỘNG TRỞ LẠI, TUY NHIÊN SỐ LƯỢNG SUBMIT BỊ GIỚI HẠN MỖI NGÀY CÒN RẤT ÍT (THEO CHÍNH SÁCH MỚI CỦA JUDGE0, BÊN CUNG CẤP API). DO VẬY RẤT MONG CÁC BẠN CHÚ Ý TEST THẬT KỸ CODE TRƯỚC KHI SUBMIT.

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!

2 Comments

Add a Comment