CSES - Cyclic Array | Dãy tuần hoàn

Xem PDF



Tác giả:
Dạng bài
Đ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\)\(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\)\(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]\)\([2,1,2]\) (nhớ rằng mảng là tuần hoàn).

Bình luận


  • 0
    Thanh72 10:09 a.m. 19 Tháng 8, 2023 chỉnh sửa 3

    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\)\(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

    • Dòng đầu tiên chứa số nguyên \(n(1 \leq n \leq 2 \times 10^5)\)\(k(1 \leq k \leq 2 \times 10^{18})\).
    • Dòng tiếp theo chứa n số nguyên \(x_1, x_2, ..., x_n(x_i \leq k), (1 \leq x_i \leq 2 \times 10^9)\).

    Output

    • Gồm một dòng chứa số mảng con tối thiểu.

    Test 1

    Input
    8 5
    2 2 2 1 3 1 2 1
    Output
    3