WOSUB - Đoạn con thách đố
Xem dạng PDF
Gửi bài giải
Điểm:
1,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C#, C++, Go, Java, Pascal, Perl, PHP, PyPy, Python, Ruby, Rust, Scratch, Swift
Wo và Row là đôi bạn cùng tiến của nhau. Cả 2 đều thuộc Đội tuyển dự thi học sinh giỏi Quốc gia của tỉnh. Họ thường thách đố nhau bằng các bài toán Tin học. Vì điểm cao hơn Wo trong đợt tuyển chọn vừa rồi, với bản tính “thích cà khịa”, thừa thắng xông lên, Row đưa ra một bài toán và đố Wo giải được. Lần này Wo quyết định không để thua Row nữa. Bài toán của Row như sau:
- Cho một dãy gồm ~N~ số nguyên dương ~a_1, a_2, ..., a_n~ và số nguyên dương ~S~. Cần tìm độ dài đoạn con liên tiếp dài nhất có tổng bằng ~S~.
Bạn hãy lập trình giúp Wo tìm được lời giải tối ưu để Wo có thể giành chiến thắng trước Row nhé!
Input
- Dòng 1: số nguyên dương~N~(~1 ≤ N ≤ 10^5~) là số phần tử của dãy ~a~.
- Dòng 2:~N~số nguyên dương~a_i~(~1 ≤ i ≤ N; 1 ≤ a_i ≤ 1000~) là các phần tử của dãy ~a~.
- Dòng 3: số nguyên dương~S~.
Output
- Một số nguyên ~k~ duy nhất là độ dài đoạn con liên tiếp dài nhất có tổng bằng~S~
- Trường hợp không tìm được dãy con nào thoả mãn,in ra -1
Sample
Input #1
5
1 2 3 4 5
12
Output #1
3
Input #2
9
3 5 5 5 5 4 3 2 1
15
Output #2
5
Input #3
4
2 3 5 7
9
Output #3
-1
Hint
Ràng buộc:
- Subtask 1:30% tests có n <= 100
- Subtask 2:30% tests có n <= 3000
- Subtask 3:40% tests còn lại có n <= 100000
Giải thích:
- Ở test ví dụ 1, chỉ có dãy [3,4,5] thoả mãn nên đáp số là 3.
- Test ví dụ 2 có 3 dãy con thoả mãn là [5,5,5], [5,5,5] và [5,4,3,2,1]. Đáp số tối ưu là 5.
- Test ví dụ 3 không có dãy con liên tiếp nào có tổng bằng 9 nên đáp số là -1.
Problem source: bvquoc
Bình luận
Tư tưởng của bài này như này (C++) : -Thay vì t dùng cách tạo mảng cộng dồng prefsum , rồi duyệt 2 vòng for để tìm đoạn dài nhất có tổng = S thì sẽ tốn O(n^2)=> chắc chắn bị TLE từ test 30 -Ta sẽ dùng 1 cách hay hơn chỉ tốn O(n) bằng unorderedmap (cái này sẽ giúp mình tìm nhanh hơn là map -vì nó tìm kiếm ngẫu nhiên ):Đầu tiên ta tạo unorderedmap<long long,int>mp ; mp [0]=-1;(lưu tổng 0 sẽ tại vị trí -1 ) +B1:Tạo 1 thằng sum để lưu tổng các đoạn từ [a[0],a[i]) +B2:sau khi sum +a[i] xong ta xét >nếu tìm thấy phần tử (sum - S) (ở trong mp )thì kết quả là max của (kết quả cũ và hiệu giữa i hiện tại và mp[sum -S]) =>result=max(result,i-mp[sum-s])
ez mak