Tìm dãy tổng liên tiếp

Xem dạng PDF
Gửi bài giải
Điểm: 18,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout
Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Cho dãy số nguyên dương a có ~n~ phần tử. Hãy tìm độ dài đoạn con dài nhất trong dãy sao cho tổng các phần tử trong đoạn này không quá ~s~. Dữ liệu đảm bảo các phần tử trong dãy a đều có giá trị không quá ~s~.

Input:

  • Dòng 1. Ghi 2 số nguyên dương ~n~, ~s~.
  • Dòng 2. Ghi n số nguyên ~a_1, a_2,...,a_n~

Output:

  • Ghi ra độ dài của dãy con dài nhất thoả mãn yêu cầu trên.

Example:

Input:

7 20
2 6 5 3 6 8 9

Output:

4

Constraints:

~n \le 10^6; 0 \le a_i \le 10^9; s \le 10^{18}~

Bình luận

Hãy đọc nội quy trước khi bình luận.


  • 0
    memaybeocomvn  đã bình luận lúc 15, Tháng 10, 2024, 9:55

    ............


  • -2
    Shinoz  đã bình luận lúc 26, Tháng 8, 2023, 15:20 ← chỉnh sửa

    Solution By Shinoz

    Hint 1 - Prefix Sum ( TLE )

    Chạy vòng lặp đọc các phần tử trong mảng và lưu vào mảng cộng dồn

    Chạy vòng lặp lồng để kiểm tra tổng từ i -> j có <= s hay không, nếu có lấy biến max lưu khoảng cách của i -> j (j - i + 1)

    Hint 2 - Two pointer ( AC )

    Lấy biến max = 0, sum = 0, j = 0

    Chạy vòng lặp i từ 1 -> n:

    Liên tục cập nhật tổng sum = sum + a[i]

    Nếu tổng sum > s thì ta cộng j lên 1 đơn vị và giảm tổng sum đi a[j] và cập nhật max = i - j

    Nếu bí quá có thể liên hệ mình để hỏi rõ và lấy code tại đây


    • -7
      ht_maths2512  đã bình luận lúc 26, Tháng 10, 2023, 11:55

      Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


      • -1
        abcnickname  đã bình luận lúc 2, Tháng 10, 2024, 9:04

        ohno anh shinoz troll troll roi


        • -2
          abcnickname  đã bình luận lúc 3, Tháng 10, 2024, 8:11

          cái phần ma=i-j bị sai nha sau khi kết thức thì in ra i-j-1 >:)


      • -3
        EvolutionOfLearning  đã bình luận lúc 1, Tháng 12, 2023, 4:02

        skibidi dop dop yes yes


  • -11
    khoi1503  đã bình luận lúc 26, Tháng 8, 2023, 13:42

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.