CSES - Cyclic Array | Dãy tuần hoàn
Xem PDF
Điểm:
1900 (p)
Thời gian:
1.0s
Bộ nhớ:
512M
Input:
bàn phím
Output:
màn hình
Bạn được cho một mảng tuần hoàn gồm \(n\) giá trị. Mỗi phần tử có 2 hàng xóm, các phần tử ở vị trí \(n\) và \(1\) cũng được coi là hàng xóm.
Nhiệm vụ của bạn là chia mảng thành các mảng con sao cho tổng các số trong mỗi mảng con không lớn hơn \(k\). Hỏi số lượng mảng con tối thiểu là bao nhiêu?
Input
- Dòng đầu tiên chứa số nguyên \(n\) và \(k\).
- Dòng tiếp theo chứa n số nguyên \(x_1, x_2, ..., x_n\). Các phần tử trong mảng không lớn hơn \(k\).
Output
- In ra một số: số mảng con tối thiểu.
Constraints
- \(1 \le n \le 2 \times 10^5\).
- \(1 \le x_i \le 2 \times 10^9\).
- \(1 \le k \le 2 \times 10^{18}\).
Example
Sample input
8 5
2 2 2 1 3 1 2 1
Sample output
3
Note
- Giải thích: chúng ta có thể tạo ra \(3\) mảng con: \([2,2,1]\), \([3,1]\) và \([2,1,2]\) (nhớ rằng mảng là tuần hoàn).
Bình luận
Bạn được cho một mảng tuần hoàn gồm \(n\) giá trị. Mỗi phần tử có 2 hàng xóm, hai phần tử ở vị trí \(1\) và \(n\) cũng được coi là hàng xóm với nhau.
Bạn cần chia mảng thành các mảng con sao cho tổng các số trong mỗi mảng con không lớn hơn \(k\). Hỏi số lượng mảng con tối thiểu là bao nhiêu?
Input
Output
Test 1
Input
Output