CSES - Subarray Sums I | Tổng đoạn con I
Xem PDF
Điểm:
1000 (p)
Thời gian:
1.0s
Bộ nhớ:
512M
Input:
bàn phím
Output:
màn hình
Cho một mảng gồm \(n\) số nguyên dương, nhiệm vụ của bạn là đếm số lượng đoạn con có tổng \(x\).
Input
- Dòng đầu vào đầu tiên có hai số nguyên \(n\) và \(x\): kích thước của mảng và tổng \(x\).
- Dòng tiếp theo có \(n\) số nguyên \(a_1, a_2, \ldots, a_n\): nội dung của mảng.
Output
- In một số nguyên: số lượng đoạn con được yêu cầu.
Constraints
- \(1 \le n \le 2 \cdot 10^5\)
- \(1 \le x, a_i \le 10^9\)
Example
Sample input
5 7
2 4 1 2 7
Sample output
3
Bình luận
Hint giải: Mỗi phần tử mảng a>=1 cho nên nếu tổng>m thì trừ ở vị trí bắt đầu tổng
Còn nếu Ai=m thì kết thúc tổng và bắt đầu tổng mới
Để giải bài toán đếm số lượng đoạn con có tổng x từ một mảng n số nguyên dương, ta có thể sử dụng thuật toán như sau:
Khởi tạo biến count để đếm số lượng đoạn con thỏa mãn.
Duyệt qua từng phần tử trong mảng và tính tổng từ phần tử hiện tại đến từng phần tử khác.
Nếu tổng bằng x, tăng biến count lên 1.
In ra giá trị của biến count là số lượng đoạn con thỏa mãn.
Với ví dụ trong đề, mảng là [2, 4, 1, 2, 7] và x = 7, số lượng đoạn con có tổng bằng 7 là 3.
ai cho mình gợi ý được không, mình dùng mảng cộng dồn vẫn chưa ac