Dãy số
Xem dạng PDF
Gửi bài giải
Điểm:
0,10 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
512M
Input:
stdin
Output:
stdout
Nguồn bài:
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch
Cho dãy số nguyên a1, a2, ..., an (~1 \leq n \leq 100000~), mỗi số không vượt quá 10000. Dãy số này được viết trên một vòng tròn. Nghĩa là, khi cắt vòng tròn tại vị trí j, ta thu được:
~a_{j}~, ~a_{j+1}~,..., ~a_{n}~, ~a_1~, ~a_2~, ..., ~a_{j-1}~
Vị trí j được gọi là vị trí tốt, nếu các điều kiện sau đây được thỏa mãn:
- ~a_{j}~ ~>~ 0
- ~a_{j}~ + ~a_{j+1}~ ~>~ 0
- ....
- ~a_{j}~ + ~a_{j+1}~ + ... + ~a_{n}~ ~>~ 0
- ~a_{j}~ + ~a_{j+1}~ + ... + ~a_{n}~ + ~a_1~ ~>~ 0
- ...
- ~a_{j}~ + ~a_{j+1}~ + ... + ~a_{n}~ + ~a_1~ + ~a_2~ + ... + ~a_{j─2}~ ~>~ 0
- ~a_{j}~ + ~a_{j+1}~ + ... + ~a_{n}~ + ~a_1~ + ~a_2~ + ... + ~a_{j─2}~ + ~a_{j─1}~ ~>~ 0
Yêu cầu: hãy đếm số vị trí tốt.
Input
- Dòng đầu tiên chứa số nguyên n.
- Dòng thứ 2 chứa dãy số ~a_1~, ~a_2~,...,~a_{n}~.
Output
- In ra 1 số nguyên duy nhất là số vị trí tốt.
Sample Input
5
0 1 -2 10 3
Sample Output
2
Bình luận
trước từ đề bài dễ thấy ta cần kéo mảng có độ dài n thành 2*n . Sau đó tính cái prefix sum như bình thường thôi.
như vậy tại 1 vị trí j ta cần điều kiện a[j]+a[j+1]+a[j+2]+...+a[k]>0 (j<=k<=j+n-1)
Gọi S[k]=a[j]+a[j+1]+a[j+2]+...+a[k], vị trí j được gọi là tốt nhất khi và chỉ khi min(S[k])>0 với (j<=k<=j+n-1)
hay min(S[k]-S[j-1])>0 (j<=k<=j+n-1)
=> min(S[k])>S[j-1]
từ hướng này thì ta sẽ có 2 cách xử lí: có thể dùng cây phân đoạn như seg hay fenwick hoặc dùng deque. Vì trong bình luận chưa ai dùng deque thì mình sẽ làm theo hướng deque
Ta dùng deque để tìm giá trị min trong đoạn từ [j,j+n-1]. Các bạn có thể tham khảo code tìm min ở đây: Tại đây
sau đó chỉ cần với mỗi vị trí j chỉ cần xem min(S[k]) (j<=k<j+n-1) > S[j-1] hay không? nếu được thì thỏa mãn
code tham khảo: ideone
Mảng cộng dồn + multiset vị trí j thỏa mãn nếu: với mọi vị trí i (j <= i <= n) f[i] - f[j - 1] > 0. Điều này có nghĩa là không tồn tại vị trí i nào thỏa mãn f[i] - f[j - 1] <= 0 -> f[i] <= f[j - 1] Vậy ta cần 1 multiset duy trì các f[i] nằm bên phải j sau đó tìm phần tử lớn nhất <= f[j - 1] nếu không tìm được tức là thỏa mãn tương tự với 1 <= i <= j thỏa mãn: f[n] - f[j - 1] + f[i] > 0
Bạn nào dùng Segment Tree + prefixSum nhưng cứ bị sai test 2, 11, 15, 16, 18, 19, 20, 21 thì là do Segment Tree của bạn khởi tạo bị thiếu phần tử nhé. Do mảng A cũng như mảng PrefixSum độ dài 2 * MaxN. Vậy Segment Tree phải có độ dài 4 * 2 * MaxN mới đủ chứa mảng F
Hint
Solution:
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.